Submission #437138

#	Time	Username	Problem	Language	Result	Execution time	Memory
437138		sofapuden	Mutating DNA (IOI21_dna)	C++17	100 / 100	64 ms	6420 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"

using namespace std;

vector<int> match, ac, ca, at, ta, ct, tc, A, C, T;

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

int get_distance(int x, int y) {
	int ans = 0;
	int dis = y-x+1;
	if(x == 0){
		if(A[y]|C[y]|T[y])return -1;
		dis-=match[y];
		ans+=min(ac[y],ca[y]);
		ans+=min(at[y],ta[y]);
		ans+=min(tc[y],ct[y]);
		dis-=2*ans;
		return ans+(dis/3)*2;
	}
	else{
		if((A[y]-A[x-1])|(C[y]-C[x-1])|(T[y]-T[x-1]))return -1;
		dis-=match[y]-match[x-1];
		ans+=min(ac[y]-ac[x-1],ca[y]-ca[x-1]);
		ans+=min(at[y]-at[x-1],ta[y]-ta[x-1]);
		ans+=min(tc[y]-tc[x-1],ct[y]-ct[x-1]);
		dis-=2*ans;
		return ans+(dis/3)*2;
	}
}

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