Submission #437067

#	Time	Username	Problem	Language	Result	Execution time	Memory
437067		DunderMifflin	Mutating DNA (IOI21_dna)	C++17	100 / 100	74 ms	8476 KiB

dna

#include "dna.h"
#include<map>
using namespace std;

const int N = 123456;

int pref[3][3][N];
int asum[3][N];
int bsum[3][N];
map<char, int> f;

void init(std::string a, std::string b) {
	f['A'] = 0; f['C'] = 1; f['T'] = 2;
	int n = (int) a.size();
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < 3; k++) {
			asum[k][i] = 0;
			bsum[k][i] = 0;
			for (int l = 0; l < 3; l++) {
				pref[k][l][i] = 0;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (i > 0) {
			for (int k = 0; k < 3; k++) {
				for (int l = 0; l < 3; l++) {
					pref[k][l][i] = pref[k][l][i - 1];
				}
				asum[k][i] = asum[k][i - 1];
				bsum[k][i] = bsum[k][i - 1];
			}
		}
		for (int k = 0; k < 3; k++) {
			for (int l = 0; l < 3; l++) {
				pref[k][l][i] += (f[a[i]] == k && f[b[i]] == l);
			}
			asum[k][i] += (f[a[i]] == k);
			bsum[k][i] += (f[b[i]] == k);
		}
	}
}

int get_distance(int x, int y) {
	for (int t = 0; t < 3; t++) {
		int res_a = asum[t][y];
		if (x > 0) {
			res_a -= asum[t][x - 1];
		}
		int res_b = bsum[t][y];
		if (x > 0) {
			res_b -= bsum[t][x - 1];
		}
		if (res_a != res_b) return -1;
	}
	int ans = 0;
	int surplus = 0;
	for (int k = 0; k < 3; k++) {
		for (int l = k + 1; l < 3; l++) {
			int k_to_l = pref[k][l][y];
			if (x > 0) {
				k_to_l -= pref[k][l][x - 1];
			}

			int l_to_k = pref[l][k][y];
			if (x > 0) {
				l_to_k -= pref[l][k][x - 1];
			}

			ans += min(k_to_l, l_to_k);
			surplus += max(k_to_l, l_to_k) - min(k_to_l, l_to_k);
		}
	}
	return ans + ((2 * surplus) / 3);
}

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