Submission #964533

#	Time	Username	Problem	Language	Result	Execution time	Memory
964533		UmairAhmadMirza	Mutating DNA (IOI21_dna)	C++17	100 / 100	33 ms	5708 KiB

dna

#include <bits/stdc++.h>
using namespace std;
int const N=1e5+5;
int n;
string a,b;
// int preA[N],preT[N],preC[N];
int AT[N],TC[N],CA[N];
int eq[N];
void init(string aa,string bb){
	n=aa.length();
	a=aa;
	b=bb;
	for (int i = 1; i <=n; ++i)
	{
		// preA[i]=preA[i-1];
		// preT[i]=preT[i-1];
		// preC[i]=preC[i-1];
		AT[i]=AT[i-1];
		CA[i]=CA[i-1];
		TC[i]=TC[i-1];
		eq[i]=eq[i-1];
		// if(b[i-1]=='A')
		// 	preA[i]++;
		// else if(b[i-1]=='T')
		// 	preT[i]++;
		// else
		// 	preC[i]++;
		if(a[i-1]==b[i-1])
			eq[i]++;
		else if(a[i-1]=='A'&&b[i-1]=='T')
			AT[i]++;
		else if(a[i-1]=='T'&&b[i-1]=='A')
			AT[i]--;
		else if(a[i-1]=='T'&&b[i-1]=='C')
			TC[i]++;
		else if(a[i-1]=='C'&&b[i-1]=='T')
			TC[i]--;
		else if(a[i-1]=='C'&&b[i-1]=='A')
			CA[i]++;
		else
			CA[i]--;
	}
}
int get_distance(int x, int y){
	//check
	y++;
	int one=AT[y]-AT[x];
	int two=TC[y]-TC[x];
	int three=CA[y]-CA[x];
	// cout<<one<<' '<<two<<' '<<three<<endl;
	if(one!=two || one!=three)
		return -1;
	int ans=abs(one)*2;
	int tot=y-x;
	tot-=(eq[y]-eq[x]);
	tot-=abs(one)*3;
	ans+=tot/2;
	return ans;
}

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