Submission #1240928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240928		ZeroCool	Mutating DNA (IOI21_dna)	C++17	100 / 100	22 ms	6152 KiB

dna

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

const int N = 2e5 + 20;

using namespace std;

int ac[N], at[N],ca[N], ct[N], ta[N], tc[N];
int n;

int cntA[N], cntC[N], cntT[N];

void init(std::string a, std::string b) {
	n = a.size();
	for(int i = 0;i < n;i++){
		if(a[i] == 'A'){
			cntA[i]++;
			if(b[i] == 'C')ac[i]++;
			if(b[i] == 'T')at[i]++;
		}
		if(a[i] == 'C'){
			cntC[i]++;
			if(b[i] == 'A')ca[i]++;
			if(b[i] == 'T')ct[i]++;
		}
		if(a[i] == 'T'){
			cntT[i]++;
			if(b[i] == 'A')ta[i]++;
			if(b[i] == 'C')tc[i]++;
		}
		if(b[i] == 'A')cntA[i]--;
		if(b[i] == 'C')cntC[i]--;
		if(b[i] == 'T')cntT[i]--;

		if(i){
			ac[i] += ac[i - 1];
			at[i] += at[i - 1];
			ca[i] += ca[i - 1];
			ct[i] += ct[i - 1];
			ta[i] += ta[i - 1];
			tc[i] += tc[i - 1];
			cntA[i] += cntA[i - 1];
			cntC[i] += cntC[i - 1];
			cntT[i] += cntT[i - 1];
		}
	}
}

int get_distance(int x, int y) {
	int AC = ac[y];
	int AT = at[y];
	int CA = ca[y];
	int CT = ct[y];
	int TA = ta[y];
	int TC = tc[y];
	int A = cntA[y];
	int T = cntT[y];
	int C = cntC[y];
	if(x){
		--x;
		AC -= ac[x];
		AT -= at[x];
		CA -= ca[x];
		CT -= ct[x];
		TA -= ta[x];
		TC -= tc[x];
		A -= cntA[x];
		T -= cntT[x];
		C -= cntC[x];
	}
//	cout<<A<<" "<<T<<" "<<C<<'\n';
	if(A != 0 || T != 0 || C != 0)return -1;
	return min(AC, CA) + min(CT, TC) + min(TA, AT) + 2 * max(AC -  min(AC, CA), CA -  min(AC, CA));
}

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