Submission #716139

#	Time	Username	Problem	Language	Result	Execution time	Memory
716139		Baytoro	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	9944 KiB

dna

#include "dna.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
string a,b;
const int N=1e5+5;
int n;
int d[3][3][N];
int prefA[N][2],prefC[N][2],prefT[N][2];
void init(string A, string B) {
	a="#"+A;
	b="#"+B;
	n=A.size();
	for(int i=1;i<=n;i++){
		if(a[i]=='A') prefA[i][0]++;
		if(b[i]=='A') prefA[i][1]++;
		if(a[i]=='C') prefC[i][0]++;
		if(b[i]=='C') prefC[i][1]++;
		if(a[i]=='T') prefT[i][0]++;
		if(b[i]=='T') prefT[i][1]++;
		prefA[i][0]+=prefA[i-1][0];
		prefA[i][1]+=prefA[i-1][1];
		prefC[i][0]+=prefC[i-1][0];
		prefC[i][1]+=prefC[i-1][1];
		prefT[i][0]+=prefT[i-1][0];
		prefT[i][1]+=prefT[i-1][1];
	}
	for(int i=1;i<=n;i++){
		int x,y;
		if(a[i]=='A') x=0;
		else if(a[i]=='C') x=1;
		else x=2;
		if(b[i]=='A') y=0;
		else if(b[i]=='C') y=1;
		else y=2;
		for(int k=0;k<3;k++) for(int j=0;j<3;j++) d[k][j][i]+=d[k][j][i-1];
		d[x][y][i]++;
	}
}
int get_distance(int x, int y) {
	x++,y++;
	if(prefA[y][0]-prefA[x-1][0]!=prefA[y][1]-prefA[x-1][1]) return -1;
	if(prefC[y][0]-prefC[x-1][0]!=prefC[y][1]-prefC[x-1][1]) return -1;
	if(prefT[y][0]-prefT[x-1][0]!=prefT[y][1]-prefT[x-1][1]) return -1;
	int res=0,k,a,b,left=0;
	a=d[0][2][y]-d[0][2][x-1],b=d[2][0][y]-d[2][0][x-1];
	k=min(a,b);
	res+=k;
	a-=k;
	b-=k;
	left+=(a+b);
	a=d[0][1][y]-d[0][1][x-1],b=d[1][0][y]-d[1][0][x-1];
	k=min(a,b);
	res+=k;
	a-=k;
	b-=k;
	left+=(a+b);
	a=d[1][2][y]-d[1][2][x-1],b=d[2][1][y]-d[2][1][x-1];
	k=min(a,b);
	res+=k;
	a-=k;
	b-=k;
	left+=(a+b);
	return res+(left/3*2);
}

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