Submission #1137153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137153		Shadow1	Mutating DNA (IOI21_dna)	C++20	100 / 100	26 ms	7268 KiB

dna

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

#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define sz(x) int(x.size())

const int maxn = 1e5 + 5;
vector<int> ta(maxn), aa(maxn), cA(maxn), tb(maxn), ab(maxn), cB(maxn), diff(maxn);
vector<int> ct(maxn), ca(maxn), tc(maxn), ac(maxn), cc(maxn);

void init(std::string a, std::string b) {
	int n = sz(a);
	ta[0] = (a[0] == 'T');
	tb[0] = (b[0] == 'T');
	aa[0] = (a[0] == 'A');
	ab[0] = (b[0] == 'A');
	cA[0] = (a[0] == 'C');
	cB[0] = (b[0] == 'C');
	ct[0] = (a[0] == 'C' && b[0] == 'T');
	ca[0] = (a[0] == 'C' && b[0] == 'A');
	tc[0] = (a[0] == 'T' && b[0] == 'C');
	ac[0] = (a[0] == 'A' && b[0] == 'C');
	cc[0] = (a[0] == 'C' && b[0] == 'C');
	diff[0] = (b[0] != 'C' && a[0] != b[0]);
	for(int i=1; i<n; ++i) {
		ta[i] = ta[i-1] + (a[i] == 'T');
		tb[i] = tb[i-1] + (b[i] == 'T');
		aa[i] = aa[i-1] + (a[i] == 'A');
		ab[i] = ab[i-1] + (b[i] == 'A');
		cA[i] = cA[i-1] + (a[i] == 'C');
		cB[i] = cB[i-1] + (b[i] == 'C');
		ct[i] = ct[i-1] + (a[i] == 'C' && b[i] == 'T');
		ca[i] = ca[i-1] + (a[i] == 'C' && b[i] == 'A');
		tc[i] = tc[i-1] + (a[i] == 'T' && b[i] == 'C');
		ac[i] = ac[i-1] + (a[i] == 'A' && b[i] == 'C');
		cc[i] = cc[i-1] + (a[i] == 'C' && b[i] == 'C');
		diff[i] = diff[i-1];
		if(b[i] == 'C') continue;
		diff[i] += (a[i] != b[i]);
	}
}

int get_distance(int x, int y) {
	if(x == 0) {
		if(ta[y] != tb[y] || aa[y] != ab[y] || cA[y] != cB[y])
			return -1;
		else {
			int d = diff[y];
			d -= min(ct[y], tc[y]);
			d -= min(ca[y], ac[y]);
			d >>= 1;
			return d + (cA[y] - cc[y]);
		}
	} else {
		if(ta[y] - ta[x-1] != tb[y] - tb[x-1] || aa[y] - aa[x-1] != ab[y] - ab[x-1] || cA[y] - cA[x-1] != cB[y] - cB[x-1])
			return -1;
		else {
			int d = diff[y] - diff[x-1];
			d -= min(ct[y] - ct[x-1], tc[y] - tc[x-1]);
			d -= min(ca[y] - ca[x-1], ac[y] - ac[x-1]);
			d >>= 1;
			return d + (cA[y] - cA[x-1] - (cc[y] - cc[x-1]));
		}
	}
}

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