Submission #1036041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036041		Mardonbekhazratov	Mutating DNA (IOI21_dna)	C++17	56 / 100	52 ms	31044 KiB

dna

#include "dna.h"

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>>c1,c2;
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;
	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']++;
	}
}


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;
	return ((y-x+1)-dp[y+1]+dp[x]+1)/2;
}

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