Submission #493163

#	Time	Username	Problem	Language	Result	Execution time	Memory
493163		zhougz	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	7360 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

int pre[100'050][3][3];

void init(std::string a, std::string b) {
	assert(a.length() == b.length());
	const int n = a.length();
	auto id = [](char c) -> int {
		return (c == 'A' ? 0 : (c == 'C' ? 1 : 2));
	};
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				pre[i][j][k] += pre[i - 1][j][k];
			}
		}
		pre[i][id(a[i - 1])][id(b[i - 1])]++;
	}
}

int get_distance(int x, int y) {
	int arr[3][3], diff[3];
	fill(diff, diff + 3, 0);
	for (int j = 0; j < 3; j++) {
		for (int k = 0; k < 3; k++) {
			arr[j][k] = pre[y + 1][j][k] - pre[x][j][k];
			diff[j] += arr[j][k];
			diff[k] -= arr[j][k];
		}
	}
	for (int i = 0; i < 3; i++) {
		if (diff[i] != 0) {
			return -1;
		}
	}
	int res = 0;
	// Swap pairs first
	for (int j = 0; j < 3; j++) {
		for (int k = 0; k < j; k++) {
			int pair_swaps = min(arr[j][k], arr[k][j]);
			arr[j][k] -= pair_swaps;
			arr[k][j] -= pair_swaps;
			res += pair_swaps;
		}
	}
	// I believe over here there are left with only triplets
	// Furthermore the frequency that A, C, T appears should be equal
	int triplet_swaps = max(arr[0][1], arr[1][0]);
	assert(triplet_swaps == max(arr[0][2], arr[2][0]) && triplet_swaps == max(arr[1][2], arr[2][1]));
	res += 2 * triplet_swaps;
	return res;
}

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