Submission #837230

#	Time	Username	Problem	Language	Result	Execution time	Memory
837230		ma_moutahid	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	7428 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;

vi at;
vi ta;
vi ac;
vi ca;
vi tc;
vi ct;
vi A;
vi T;
vi C;
void init(std::string a, std::string b) {
	int n=a.size();
	at.resize(n);
	ac.resize(n);
	ct.resize(n);
	tc.resize(n);
	ta.resize(n);
	ca.resize(n);
	C.resize(n);
	A.resize(n);
	T.resize(n);
	for(int i=0;i<n;i++){
		if(i){
			ta[i]+=ta[i-1];ca[i]+=ca[i-1];tc[i]+=tc[i-1];ac[i]+=ac[i-1];at[i]+=at[i-1];ct[i]+=ct[i-1];
			A[i]+=A[i-1];
			C[i]+=C[i-1];
			T[i]+=T[i-1];
		}
		if(a[i]=='T'){
			T[i]++;
			if(b[i]=='A')ta[i]++;
			if(b[i]=='C')tc[i]++;
		}
		if(a[i]=='A'){
			A[i]++;
			if(b[i]=='T')at[i]++;
			if(b[i]=='C')ac[i]++;
		}
		if(a[i]=='C'){
			C[i]++;
			if(b[i]=='A')ca[i]++;
			if(b[i]=='T')ct[i]++;
		}
		if(b[i]=='A')A[i]--;
		if(b[i]=='T')T[i]--;
		if(b[i]=='C')C[i]--;
	}
}

int get_distance(int x, int y) {
	int cost=0;
	int dac=0,dat=0,dta=0,dtc=0,dca=0,dct=0;
	int a=0,t=0,c=0;
	if(x){
		dac-=ac[x-1];
		dat-=at[x-1];
		dtc-=tc[x-1];
		dta-=ta[x-1];
		dca-=ca[x-1];
		dct-=ct[x-1];
		a-=A[x-1];
		t-=T[x-1];
		c-=C[x-1];
	}
	a+=A[y];
	t+=T[y];
	c+=C[y];
	if(a || t  || c)return -1;
	dac+=ac[y];
	dat+=at[y];
	dtc+=tc[y];
	dta+=ta[y];
	dca+=ca[y];
	dct+=ct[y];

	if(dac<dca)swap(dac,dca);
	if(dat<dta)swap(dat,dta);
	if(dct<dtc)swap(dtc,dct);

	cost=dca+dta+dtc;
	int left=dac+dat+dct-cost;
	cost+=2*left/3;

	return cost;
}

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