Submission #978235

#	Time	Username	Problem	Language	Result	Execution time	Memory
978235		tamir1	Mutating DNA (IOI21_dna)	C++17	100 / 100	41 ms	8652 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
string t="#",s="#";
int n,i,A1[100005],C1[100005],T1[100005],A2[100005],C2[100005],T2[100005],AC[100005],CA[100005],AT[100005],TA[100005],CT[100005],TC[100005];
void init(std::string a, std::string b) {
	n=a.size();
	s+=a;
	t+=b;
	for(i=1;i<=n;i++){
		A1[i]=A1[i-1]+(s[i]=='A');
		C1[i]=C1[i-1]+(s[i]=='C');
		T1[i]=T1[i-1]+(s[i]=='T');
		A2[i]=A2[i-1]+(t[i]=='A');
		C2[i]=C2[i-1]+(t[i]=='C');
		T2[i]=T2[i-1]+(t[i]=='T');
		AC[i]=AC[i-1]+(s[i]=='A' && t[i]=='C');
		CA[i]=CA[i-1]+(s[i]=='C' && t[i]=='A');
		AT[i]=AT[i-1]+(s[i]=='A' && t[i]=='T');
		TA[i]=TA[i-1]+(s[i]=='T' && t[i]=='A');
		CT[i]=CT[i-1]+(s[i]=='C' && t[i]=='T');
		TC[i]=TC[i-1]+(s[i]=='T' && t[i]=='C');
	}
}
int a1,a2,c1,c2,t1,t2,ac,ca,at,ta,ct,tc,ans;
int get_distance(int x, int y) {
	ans=0;
	y++;
	a1=A1[y]-A1[x];
	a2=A2[y]-A2[x];
	c1=C1[y]-C1[x];
	c2=C2[y]-C2[x];
	t1=T1[y]-T1[x];
	t2=T2[y]-T2[x];
	
	ac=AC[y]-AC[x];
	at=AT[y]-AT[x];
	ca=CA[y]-CA[x];
	ct=CT[y]-CT[x];
	ta=TA[y]-TA[x];
	tc=TC[y]-TC[x];	
	if(a1!=a2 || c1!=c2 || t1!=t2) return -1;
	if(ac > ca) {ans+=ca,ac-=ca,ca=0;}
	else {ans+=ac,ca-=ac,ac=0;}
	if(at > ta) {ans+=ta,at-=ta,ta=0;}
	else {ans+=at,ta-=at,at=0;}
	if(ct > tc) {ans+=tc,ct-=tc,tc=0;}
	else {ans+=ct,tc-=ct,ct=0;}
	//cout << ac << " " << ct << " " << ta << "\n";
	//cout << ca << " " << at << " " << tc << "\n";
	return ans+ac*2+ca*2;
}

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