Submission #608192

#	Time	Username	Problem	Language	Result	Execution time	Memory
608192		KoD	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	7412 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

int sum[100001][3][3];

void init(std::string a, std::string b) {
	const int n = (int)a.size();
	for (int i = 0; i < n; ++i) {
		const int x = a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2);
		const int y = b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2);
		sum[i + 1][x][y] += 1;
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				sum[i + 1][j][k] += sum[i][j][k];
			}
		}
	}
}

int get_distance(int l, int r) {
	int dif[3][3];
	for (int j = 0; j < 3; ++j) {
		for (int k = 0; k < 3; ++k) {
			dif[j][k] = sum[r + 1][j][k] - sum[l][j][k];
		}
	}
	int ret = 0;
	for (int i = 0; i < 3; ++i) {
		const int j = i == 2 ? 0 : i + 1;
		const int min = std::min(dif[i][j], dif[j][i]);
		ret += min;
		dif[i][j] -= min;
		dif[j][i] -= min;
	}
	if (dif[0][1] == dif[1][2] and dif[1][2] == dif[2][0] and dif[1][0] == dif[2][1] and dif[2][1] == dif[0][2]) {
		return ret + (dif[0][1] + dif[1][0]) * 2;
	} else {
		return -1;
	}
}

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