Submission #437339

#	Time	Username	Problem	Language	Result	Execution time	Memory
437339		DunderMifflin	Mutating DNA (IOI21_dna)	C++17	100 / 100	81 ms	8544 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(); 
	a = " " + a;
	b = " " + b;
	for (int i = 1; i <= n; i++) {
		for (int k = 0; k < 3; k++) {
			for (int l = 0; l < 3; l++) {
				pref[k][l][i] = pref[k][l][i - 1] + (f[a[i]] == k && f[b[i]] == l);
			}
			asum[k][i] = asum[k][i - 1] + (f[a[i]] == k);
			bsum[k][i] = bsum[k][i - 1] + (f[b[i]] == k);
		}
	}
}

int get_distance(int x, int y) {
	x++; y++;
	for (int t = 0; t < 3; t++) {
		if (asum[t][y] - asum[t][x - 1] != bsum[t][y] - bsum[t][x - 1]) {
			return -1;
		}
	}
	int ans = 0, extra = 0;
	for (int k = 0; k < 3; k++) {
		for (int l = k + 1; l < 3; l++) {
			ans += min(pref[k][l][y] - pref[k][l][x - 1], pref[l][k][y] - pref[l][k][x - 1]);
			if (k == 0 and l == 1)
				extra = abs((pref[k][l][y] - pref[k][l][x - 1]) - (pref[l][k][y] - pref[l][k][x - 1]));
		}
	}
	return ans + 2 * extra;
}

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