Submission #576212

#	Time	Username	Problem	Language	Result	Execution time	Memory
576212		1ne	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	6240 KiB

dna

#include "dna.h"
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int>AtoC,AtoT,CtoT,CtoA,TtoA,TtoC;
void init(std::string a, std::string b) {
	int n = (int)a.length();
	AtoC.resize(n + 1,0);
	CtoT.resize(n + 1,0);
	AtoT.resize(n + 1,0);
	TtoA.resize(n + 1,0);
	CtoA.resize(n + 1,0);
	TtoC.resize(n + 1,0);
	for (int i = 0;i<n;++i){
		if (a[i] == b[i]){
			AtoC[i + 1]+=AtoC[i];
			AtoT[i + 1]+=AtoT[i];
			CtoT[i + 1]+=CtoT[i];
			CtoA[i + 1]+=CtoA[i];
			TtoA[i + 1]+=TtoA[i];
			TtoC[i + 1]+=TtoC[i];
			continue;
		}
		if (a[i] == 'A'){
			if (b[i] == 'T'){
				AtoT[i + 1]++;
			}
			else {
				AtoC[i + 1]++;
			}
		}
		else if (a[i] == 'T'){
			if (b[i] == 'C'){
				TtoC[i + 1]++;
			}
			else {
				TtoA[i + 1]++;
			}
		}
		else{
			if (b[i] == 'A'){
				CtoA[i + 1]++;
			}
			else {
				CtoT[i + 1]++;
			}
		}
		AtoC[i + 1]+=AtoC[i];
		AtoT[i + 1]+=AtoT[i];
		CtoT[i + 1]+=CtoT[i];
		CtoA[i + 1]+=CtoA[i];
		TtoA[i + 1]+=TtoA[i];
		TtoC[i + 1]+=TtoC[i];
	}
}

int get_distance(int x, int y) {
	++x;
	++y;
	int A = 0,C = 0,T = 0;
	A+=CtoA[y] - CtoA[x - 1] + TtoA[y] - TtoA[x - 1];
	A-=AtoC[y] - AtoC[x - 1] + AtoT[y] - AtoT[x - 1];
	C+=AtoC[y] - AtoC[x - 1] + TtoC[y] - TtoC[x - 1];
	C-=CtoA[y] - CtoA[x - 1] + CtoT[y] - CtoT[x - 1];
	T+=AtoT[y] - AtoT[x - 1] + CtoT[y] - CtoT[x - 1];
	T-=TtoA[y] - TtoA[x - 1] + TtoC[y] - TtoC[x - 1];
	if (A || T || C)return -1;
	int ans = min(AtoC[y] -AtoC[x-1],CtoA[y] - CtoA[x - 1]);
	ans+=min(TtoA[y] - TtoA[x - 1],AtoT[y] - AtoT[x - 1]);
	ans+=min(CtoT[y] - CtoT[x - 1],TtoC[y] - TtoC[x - 1]);
	int tempA = abs(AtoC[y] - AtoC[x - 1] - (CtoA[y] - CtoA[x - 1]));
	int tempB = abs(TtoA[y] - TtoA[x - 1] - (AtoT[y] - AtoT[x - 1]));
	int tempC = abs(CtoT[y] - CtoT[x - 1] - (TtoC[y] - TtoC[x - 1]));
	ans +=((tempA + tempB + tempC + 2)/3) * 2;
	return ans;
}

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