Submission #1200540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200540		PlayVoltz	Mutating DNA (IOI21_dna)	C++20	100 / 100	28 ms	7180 KiB

dna

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

vector <int> a1, a2, c1, c2, t1, t2, at, ta, ct, tc, ac, ca;

void init(string a, string b) {
	int n = a.size();
	a1.resize(n+1, 0);
	c1.resize(n+1, 0);
	t1.resize(n+1, 0);
	a2.resize(n+1, 0);
	c2.resize(n+1, 0);
	t2.resize(n+1, 0);
	at.resize(n+1, 0);
	ta.resize(n+1, 0);
	ca.resize(n+1, 0);
	ac.resize(n+1, 0);
	tc.resize(n+1, 0);
	ct.resize(n+1, 0);
	for (int i=0; i<n; ++i){
		a1[i+1] = a1[i];
		c1[i+1] = c1[i];
		t1[i+1] = t1[i];
		a2[i+1] = a2[i];
		c2[i+1] = c2[i];
		t2[i+1] = t2[i];
		at[i+1] = at[i];
		ta[i+1] = ta[i];
		ac[i+1] = ac[i];
		ca[i+1] = ca[i];
		tc[i+1] = tc[i];
		ct[i+1] = ct[i];
		if (a[i]==b[i]){
			continue;
		}
		if (a[i]=='T' && b[i]=='C'){
			++tc[i+1];
			++t1[i+1];
			++c2[i+1];
		}
		else if (a[i]=='T' && b[i]=='A'){
			++ta[i+1];
			++t1[i+1];
			++a2[i+1];
		}
		else if (a[i]=='C' && b[i]=='T'){
			++ct[i+1];
			++c1[i+1];
			++t2[i+1];
		}
		else if (a[i]=='C' && b[i]=='A'){
			++ca[i+1];
			++c1[i+1];
			++a2[i+1];
		}
		else if (a[i]=='A' && b[i]=='C'){
			++ac[i+1];
			++a1[i+1];
			++c2[i+1];
		}
		else if (a[i]=='A' && b[i]=='T'){
			++at[i+1];
			++a1[i+1];
			++t2[i+1];
		}
	}
}

int get_distance(int x, int y) {
	int TC = tc[y+1]-tc[x], CT=ct[y+1]-ct[x], TA=ta[y+1]-ta[x], AT=at[y+1]-at[x], AC=ac[y+1]-ac[x], CA=ca[y+1]-ca[x];
	int A1 = a1[y+1]-a1[x], A2 = a2[y+1]-a2[x], T1=t1[y+1]-t1[x], T2=t2[y+1]-t2[x], C1=c1[y+1]-c1[x], C2=c2[y+1]-c2[x];
	if (A1!=A2 || T1!=T2 || C1!=C2){
		return -1;
	}
	int val = abs(TC-CT)+abs(TA-AT)+abs(AC-CA);
	val*=2;
	val/=3;
	val+=min(TC, CT)+min(TA, AT)+min(AC, CA);
	return val;
}

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