Submission #1069969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069969		ihceker	Mutating DNA (IOI21_dna)	C++17	100 / 100	31 ms	6932 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"

using namespace std;

vector<vector<int>>pre(7);

void init(string a,string b){
	int n=a.size();
	for(int i=0;i<7;i++){
		pre[i].resize(n+1);
	}
	auto get_ind=[&](char x,char y)->int{
		if(x==y)return 0;
		if(x=='A'){
			if(y=='C')return 1;
			return 2;
		}
		if(x=='C'){
			if(y=='A')return 3;
			return 4;
		}
		if(y=='A')return 5;
		return 6;
	};
	for(int i=0;i<n;i++){
		for(int j=0;j<7;j++){
			pre[j][i+1]=pre[j][i];
		}
		pre[get_ind(a[i],b[i])][i+1]++;
	}
}

int get_distance(int x,int y){
	x++,y++;
	vector<int>cnt(7);
	for(int i=0;i<7;i++){
		cnt[i]=pre[i][y]-pre[i][x-1];
	}
	if(cnt[1]+cnt[2]!=cnt[3]+cnt[5] || cnt[3]+cnt[4]!=cnt[1]+cnt[6] || cnt[5]+cnt[6]!=cnt[2]+cnt[4]){
		return -1;
	}
	int a=min(cnt[1],cnt[3]),b=min(cnt[2],cnt[5]),c=min(cnt[4],cnt[6]);
	return a+b+c+(y-x+1-(a+b+c)*2-cnt[0])*2/3;
}

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16