Submission #480692

#	Time	Username	Problem	Language	Result	Execution time	Memory
480692		Haidara	Mutating DNA (IOI21_dna)	C++17	100 / 100	41 ms	8920 KiB

dna

#include<bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define FOR(i,n) rep(i,0,n)
using namespace std;
const int maxn=100200;
int t[2][maxn],a[2][maxn],c[2][maxn],tc[maxn],ct[maxn],at[maxn],ta[maxn],ac[maxn],ca[maxn];
void compute(string s,int inx)
{
	int n=s.size();
	FOR(i,n)
	{
		a[inx][i+1]=a[inx][i]+(int)(s[i]=='A');
		t[inx][i+1]=t[inx][i]+(int)(s[i]=='T');
		c[inx][i+1]=c[inx][i]+(int)(s[i]=='C');
	}
}
string s,l;
void init(string x, string y) 
{
	s=x,l=y;
	compute(x,0);
	compute(y,1);
	int n=x.size();
	FOR(i,n)
	{
		ta[i+1]=ta[i]+(int)(s[i]=='T'&&l[i]=='A');
		at[i+1]=at[i]+(int)(s[i]=='A'&&l[i]=='T');
		ac[i+1]=ac[i]+(int)(s[i]=='A'&&l[i]=='C');
		ca[i+1]=ca[i]+(int)(s[i]=='C'&&l[i]=='A');
		tc[i+1]=tc[i]+(int)(s[i]=='T'&&l[i]=='C');
		ct[i+1]=ct[i]+(int)(s[i]=='C'&&l[i]=='T');
	}
}
int get_distance(int x,int y)
{
	x++,y++;
	if(t[0][y]-t[0][x-1]!=t[1][y]-t[1][x-1]||
		c[0][y]-c[0][x-1]!=c[1][y]-c[1][x-1]||
		a[0][y]-a[0][x-1]!=a[1][y]-a[1][x-1])
		return -1;
	int ans=0;
	int TC=tc[y]-tc[x-1];
	int CT=ct[y]-ct[x-1];
	int AC=ac[y]-ac[x-1];
	int CA=ca[y]-ca[x-1];
	int TA=ta[y]-ta[x-1];
	int AT=at[y]-at[x-1];
	int dx;
	dx=max(AT,TA)-abs(AT-TA);
	ans+=dx;
	AT-=dx;
	TA-=dx;
	dx=max(AC,CA)-abs(AC-CA);
	ans+=dx;
	AC-=dx;
	CA-=dx;
	dx=max(CT,TC)-abs(TC-CT);
	ans+=dx;
	TC-=dx;
	CT-=dx;
	ans+=((TC+CT+AT+TA+CA+AC)*2)/3;
	return ans;
}

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