Submission #806014

#	Time	Username	Problem	Language	Result	Execution time	Memory
806014		pavement	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	6256 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

int pf[6][100005], cur[6];
char p[] = {'A', 'A', 'C', 'C', 'T', 'T'};
char q[] = {'C', 'T', 'A', 'T', 'A', 'C'};

void init(string a, string b) {
	for (int k = 0; k < 6; k++) {
		for (int i = 0; i < (int)a.size(); i++) {
			pf[k][i] = i ? pf[k][i - 1] : 0;
			if (a[i] == p[k] && b[i] == q[k]) {
				pf[k][i]++;
			}
		}
	}
}

int reduce(int &x, int &y) {
	int z = min(x, y);
	x -= z;
	y -= z;
	return z;
}

int get_distance(int x, int y) {
	for (int k = 0; k < 6; k++) {
		cur[k] = pf[k][y] - (x ? pf[k][x - 1] : 0);
	}
	int ans = 0;
	ans += reduce(cur[0], cur[2]);
	ans += reduce(cur[1], cur[4]);
	ans += reduce(cur[3], cur[5]);
	if (cur[1] != cur[5] || cur[5] != cur[2]) return -1;
	if (cur[0] != cur[3] || cur[3] != cur[4]) return -1;
	ans += cur[1] * 2;
	ans += cur[0] * 2;
	return ans;
}

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