Submission #783513

#	Time	Username	Problem	Language	Result	Execution time	Memory
783513		Sir_Ahmed_Imran	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	7404 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
int aA[MAXN];
int aC[MAXN];
int aT[MAXN];
int bA[MAXN];
int bC[MAXN];
int bT[MAXN];
int at[MAXN];
int ac[MAXN];
int ta[MAXN];
int tc[MAXN];
int ca[MAXN];
int ct[MAXN];
void init(std::string a, std::string b) {
	at[0]=0;
	ac[0]=0;
	ta[0]=0;
	tc[0]=0;
	ca[0]=0;
	ct[0]=0;
	aA[0]=0;
	aC[0]=0;
	aT[0]=0;
	bA[0]=0;
	bC[0]=0;
	bT[0]=0;
	int n=a.size();
	for(int i=0;i<n;i++){
		at[i+1]=at[i];
		ac[i+1]=ac[i];
		ta[i+1]=ta[i];
		tc[i+1]=tc[i];
		ca[i+1]=ca[i];
		ct[i+1]=ct[i];
		aA[i+1]=aA[i]+(a[i]=='A');
		aT[i+1]=aT[i]+(a[i]=='T');
		aC[i+1]=aC[i]+(a[i]=='C');
		bA[i+1]=bA[i]+(b[i]=='A');
		bT[i+1]=bT[i]+(b[i]=='T');
		bC[i+1]=bC[i]+(b[i]=='C');
		at[i+1]+=(a[i]=='A' && b[i]=='T');
		ac[i+1]+=(a[i]=='A' && b[i]=='C');
		ta[i+1]+=(a[i]=='T' && b[i]=='A');
		tc[i+1]+=(a[i]=='T' && b[i]=='C');
		ca[i+1]+=(a[i]=='C' && b[i]=='A');
		ct[i+1]+=(a[i]=='C' && b[i]=='T');
	}
}
int get_distance(int y, int x) {
	int Aa,At,Ac,Ba,Bt,Bc,a,b,n,m,o,p,q,r;
	o=0;
	a=at[x+1]-at[y];
	n=ac[x+1]-ac[y];
	b=ta[x+1]-ta[y];
	p=tc[x+1]-tc[y];
	m=ca[x+1]-ca[y];
	q=ct[x+1]-ct[y];
	Aa=aA[x+1]-aA[y];
	At=aT[x+1]-aT[y];
	Ac=aC[x+1]-aC[y];
	Ba=bA[x+1]-bA[y];
	Bt=bT[x+1]-bT[y];
	Bc=bC[x+1]-bC[y];
	if(Aa!=Ba || At!=Bt || Ac!=Bc)
		return -1;
	r=min(a,b);
	a-=r;
	b-=r;
	o+=r;
	r=min(n,m);
	n-=r;
	m-=r;
	o+=r;
	r=min(p,q);
	p-=r;
	q-=r;
	o+=r;
	return o+max(a,b)*2;
}

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