Submission #1354897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354897		AMnu	Mutating DNA (IOI21_dna)	C++20	100 / 100	19 ms	4216 KiB

dna

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

const int MAXN = 1e5+5;

int P[MAXN][4];

void init(string a,string b) {
	for (int i=a.size()-1;i>=0;i--) {
		for (int j=0;j<4;j++) P[i][j] = P[i+1][j];
		int x = (a[i]-b[i]+21)%3;
		if (!x) continue;
		P[i][3]++;
		P[i][(a[i]+b[i])%3] += x*2-3;
	}
}

int get_distance(int x,int y) {
	int a = P[x][0]-P[y+1][0];
	for (int i=1;i<3;i++) {
		if (P[x][i]-P[y+1][i] != a) return -1;
	}
	return (P[x][3]-P[y+1][3]+abs(a))>>1;
}

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