Submission #1209566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209566		bangan	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	6920 KiB

dna

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

constexpr int N = 1E5 + 4;

int n;
int A[N];
int B[N];
int pre[N][3][3];

int cnt[3][3];
void fill_with(int l, int r) {
	memset(cnt, 0, sizeof cnt);
	for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) cnt[x][y] = pre[r+1][x][y] - pre[l][x][y];
}

void init(std::string a, std::string b) {
	n = a.size();
	for (int i = 0; i < n; i++) {
		if (a[i] == 'A') A[i]=0;
		if (a[i] == 'C') A[i]=1;
		if (a[i] == 'T') A[i]=2;
	}
	for (int i = 0; i < n; i++) {
		if (b[i] == 'A') B[i]=0;
		if (b[i] == 'C') B[i]=1;
		if (b[i] == 'T') B[i]=2;
	}
	for (int i = 0; i < n; i++) {
		for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) pre[i + 1][x][y] = pre[i][x][y];
		pre[i + 1][A[i]][B[i]]++;
	}
}

int get_distance(int x, int y) {
	fill_with(x, y);

	if (cnt[0][1] + cnt[0][2] != cnt[1][0] + cnt[2][0]) return -1;
	if (cnt[1][0] + cnt[1][2] != cnt[0][1] + cnt[2][1]) return -1;
	if (cnt[2][0] + cnt[2][1] != cnt[0][2] + cnt[1][2]) return -1;

	int ans=0;
	int t = min(cnt[0][1], cnt[1][0]);
	cnt[0][1] -= t; cnt[1][0] -= t; ans += t;

	t = min(cnt[0][2], cnt[2][0]);
	cnt[0][2] -= t; cnt[2][0] -= t; ans += t;

	t = min(cnt[1][2], cnt[2][1]);
	cnt[1][2] -= t; cnt[2][1] -= t; ans += t;

	int add=0;
	for (int x=0; x<3; x++) for (int y=0; y<3; y++) if (x!=y) add += cnt[x][y];
	(add /= 3) *= 2;

	return ans += add;
}

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