Submission #551280

#	Time	Username	Problem	Language	Result	Execution time	Memory
551280		Pherokung	Mutating DNA (IOI21_dna)	C++17	21 / 100	35 ms	6248 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int a[N][3],b[N][3],dif[N],len;
void init(string x, string y) {
	len = x.size();
	for(int i=0;i<len;i++){
		if(i != 0) for(int j=0;j<=2;j++) a[i][j] = a[i-1][j], b[i][j] = b[i-1][j];
		if(i != 0) dif[i] = dif[i-1];
		if(x[i] == 'A') a[i][0]++;
		else if(x[i] == 'T') a[i][1]++;
		else if(x[i] == 'C') a[i][2]++;
		if(y[i] == 'A') b[i][0]++;
		else if(y[i] == 'T') b[i][1]++;
		else if(y[i] == 'C') b[i][2]++;
		if(x[i] != y[i]) dif[i]++;
	}
}

int get_distance(int x, int y) {
	int A[3], B[3], D;
	for(int i=0;i<=2;i++) A[i] = a[y][i], B[i] = b[y][i];
	if(x != 0) for(int i=0;i<=2;i++) A[i] -= a[x-1][i], B[i] -= b[x-1][i];
	for(int i=0;i<=2;i++) if(A[i] != B[i]) return -1;
	D = dif[y];
	if(x != 0) D -= dif[x-1];
	return D ? D-1 : 0;
}

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