Submission #439317

#	Time	Username	Problem	Language	Result	Execution time	Memory
439317		nandonathaniel	Mutating DNA (IOI21_dna)	C++17	56 / 100	46 ms	5248 KiB

dna

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

int N;
char ch[]={'A','C','T'};
int prefA[100005][3],prefB[100005][3],pref[100005];

void init(std::string a, std::string b) {
	N=a.length();
	for(int i=1;i<=N;i++){
		for(int j=0;j<3;j++){
			prefA[i][j]=prefA[i-1][j];
			prefB[i][j]=prefB[i-1][j];
			if(a[i-1]==ch[j]){
				prefA[i][j]++;
			}
			if(b[i-1]==ch[j]){
				prefB[i][j]++;
			}
		}
		pref[i]=pref[i-1]+(a[i-1]!=b[i-1]);
	}
}

int get_distance(int x, int y) {
	x++;y++;
	for(int i=0;i<3;i++){
		if(prefA[y][i]-prefA[x-1][i]!=prefB[y][i]-prefB[x-1][i])return -1;
	}
	return (pref[y]-pref[x-1]+1)/2;
}

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