Submission #565165

#	Time	Username	Problem	Language	Result	Execution time	Memory
565165		teraqqq	Mutating DNA (IOI21_dna)	C++17	100 / 100	64 ms	9736 KiB

dna

#include <bits/stdc++.h>

#include "dna.h"

using namespace std;

const int N = 1e5+7;

int cnt[3][3][N], cnta[3][N], cntb[3][N];
int id[256];

void init(std::string a, std::string b) {
	id['A'] = 0;
	id['C'] = 1;
	id['T'] = 2;

	const int n = a.size();
	for (int i = 0; i < n; ++i) {
		const int x = id[(int)a[i]], y = id[(int)b[i]];
		
		for (int p = 0; p < 3; ++p) {
			cnta[p][i+1] = cnta[p][i];
			cntb[p][i+1] = cntb[p][i];
			for (int q = 0; q < 3; ++q) cnt[p][q][i+1] = cnt[p][q][i];
		}

		cnt[x][y][i+1]++;
		cnta[x][i+1]++;
		cntb[y][i+1]++;
	}
}

int get_distance(int x, int y) {
	++y; // [x, y)

	for (int i = 0; i < 3; ++i) {
		if (cnta[i][y] - cnta[i][x] != cntb[i][y] - cntb[i][x]) return -1;
	}

	vector q(3, vector<int>(3));
	for (int i = 0; i < 3; ++i)
	for (int j = 0; j < 3; ++j) {
		q[i][j] = cnt[i][j][y] - cnt[i][j][x];
		if (i == j) q[i][j] = 0;
	}

	int ans = 0;

	for (int s = 0; s < 3; ++s)
	for (int t = 0; t < s; ++t) {
		int delta = min(q[s][t], q[t][s]);
		ans += delta;
		q[s][t] -= delta;
		q[t][s] -= delta;
	}

	int lam = 0;
	for (auto& u : q) for (int x : u) lam += x;
	ans += lam / 3 * 2;

	return ans;
}

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