Submission #439591

#	Time	Username	Problem	Language	Result	Execution time	Memory
439591		nandonathaniel	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	7688 KiB

dna

#include "dna.h"
#include "bits/stdc++.h"
using namespace std;

int N;
char ch[]={'A','C','T'};
int prefA[100005][3],prefB[100005][3],pref[100005],prefp[100005][6];

void init(std::string a, std::string b) {
	N=a.length();
	for(int i=1;i<=N;i++){
		for(int j=0;j<3;j++){
			prefA[i][j]=prefA[i-1][j];
			prefB[i][j]=prefB[i-1][j];
			if(a[i-1]==ch[j]){
				prefA[i][j]++;
			}
			if(b[i-1]==ch[j]){
				prefB[i][j]++;
			}
		}
		pref[i]=pref[i-1]+(a[i-1]!=b[i-1]);
		prefp[i][0]=prefp[i-1][0];
		if(a[i-1]==ch[0] && b[i-1]==ch[1])prefp[i][0]++;
		prefp[i][1]=prefp[i-1][1];
		if(a[i-1]==ch[1] && b[i-1]==ch[0])prefp[i][1]++;
		prefp[i][2]=prefp[i-1][2];
		if(a[i-1]==ch[0] && b[i-1]==ch[2])prefp[i][2]++;
		prefp[i][3]=prefp[i-1][3];
		if(a[i-1]==ch[2] && b[i-1]==ch[0])prefp[i][3]++;
		prefp[i][4]=prefp[i-1][4];
		if(a[i-1]==ch[1] && b[i-1]==ch[2])prefp[i][4]++;
		prefp[i][5]=prefp[i-1][5];
		if(a[i-1]==ch[2] && b[i-1]==ch[1])prefp[i][5]++;	
	}
}

int get_distance(int x, int y) {
	x++;y++;
	for(int i=0;i<3;i++){
		if(prefA[y][i]-prefA[x-1][i]!=prefB[y][i]-prefB[x-1][i])return -1;
	}
	int beda=pref[y]-pref[x-1];
	int ans=0;
	beda-=2*min(prefp[y][0]-prefp[x-1][0],prefp[y][1]-prefp[x-1][1]);
	ans+=min(prefp[y][0]-prefp[x-1][0],prefp[y][1]-prefp[x-1][1]);
	beda-=2*min(prefp[y][2]-prefp[x-1][2],prefp[y][3]-prefp[x-1][3]);
	ans+=min(prefp[y][2]-prefp[x-1][2],prefp[y][3]-prefp[x-1][3]);
	beda-=2*min(prefp[y][4]-prefp[x-1][4],prefp[y][5]-prefp[x-1][5]);
	ans+=min(prefp[y][4]-prefp[x-1][4],prefp[y][5]-prefp[x-1][5]);
	ans+=(beda/3)*2;
	return ans;
}

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