Submission #1036045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036045		Mardonbekhazratov	Mutating DNA (IOI21_dna)	C++17	100 / 100	85 ms	36504 KiB

dna

#include "dna.h"

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>>c1,c2,cnt;
vector<int>dp;

void init(std::string a, std::string b) {
	n=a.size();
	dp.resize(n+1);
	dp[0]=0;
	c1.assign(n+1,vector<int>(26,0));
	c2=c1;
	cnt.assign(n+1,vector<int>(6,0));
	for(int i=0;i<n;i++){
		dp[i+1]=dp[i]+(a[i]==b[i]);
		// cout<<dp[i+1]<<' ';
		c1[i+1]=c1[i];
		c1[i+1][a[i]-'A']++;
		c2[i+1]=c2[i];
		c2[i+1][b[i]-'A']++;
		cnt[i+1]=cnt[i];
		if(a[i]=='A'){
			if(b[i]=='C') cnt[i+1][0]++;
			if(b[i]=='T') cnt[i+1][1]++;
		}
		if(a[i]=='C'){
			if(b[i]=='A') cnt[i+1][2]++;
			if(b[i]=='T') cnt[i+1][3]++;
		}
		if(a[i]=='T'){
			if(b[i]=='A') cnt[i+1][4]++;
			if(b[i]=='C') cnt[i+1][5]++;
		}
		// for(int j=0;j<6;j++) cout<<cnt[i+1][j]<<" \n"[j==5];
	}
}


int get_distance(int x, int y) {
	for(int i=0;i<26;i++) if(c1[y+1][i]-c1[x][i]!=c2[y+1][i]-c2[x][i]) return -1;
	auto g=cnt[y+1];
	for(int i=0;i<6;i++) g[i]-=cnt[x][i];
	int ans=min(g[0],g[2])+min(g[1],g[4])+min(g[3],g[5])+(abs(g[0]-g[2])+abs(g[1]-g[4])+abs(g[3]-g[5]))/3*2;
	return ans;
}

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