Submission #1232651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232651		rythm_of_knight	Mutating DNA (IOI21_dna)	C++17	100 / 100	38 ms	8356 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 1e5 + 5;
int p[9][N], ha[3][N], hb[3][N], n;
vector <string> v;

void init(string a, string b) {
	string tmp = "ACT";
	for (char a : tmp) {
		for (char b : tmp) {
			string res;
			res.push_back(a);
			res.push_back(b);
			v.push_back(res);
		}
	}
	sort(all(v));
	n = a.size();
	a = "1" + a;
	b = "1" + b;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++)
			ha[j][i] = ha[j][i - 1], hb[j][i] = hb[j][i - 1];
		ha[lower_bound(all(tmp), a[i]) - tmp.begin()][i]++;
		hb[lower_bound(all(tmp), b[i]) - tmp.begin()][i]++;
		for (int j = 0; j < 9; j++)
			p[j][i] = p[j][i - 1];
		string temp;
		temp.push_back(a[i]);
		temp.push_back(b[i]);
		int k = lower_bound(all(v), temp) - v.begin();
		p[k][i]++;
	}
}

int get_distance(int x, int y) {
	swap(x, y);
	x++, y++;
	for (int i = 0; i < 3; i++)
		if (ha[i][x] - ha[i][y - 1] != hb[i][x] - hb[i][y - 1])
			return -1;
	vector <int> cnt(9);
	int len = x - y + 1, ans = 0;
	for (int i = 0; i < 9; i++) {
		cnt[i] = p[i][x] - p[i][y - 1];
		if (i % 3 == i / 3)
			len -= cnt[i], cnt[i] = 0;;
	}
	string tmp = "ACT";
	for (int i = 0; i < 3; i++) {
		for (int j = i + 1; j < 3; j++) {
			string ta, tb;
			ta.push_back(tmp[i]);
			ta.push_back(tmp[j]);
			tb.push_back(tmp[j]);
			tb.push_back(tmp[i]);
			int ka = lower_bound(all(v), ta) - v.begin();
			int kb = lower_bound(all(v), tb) - v.begin();
			int mn = min(cnt[ka], cnt[kb]);
			ans += mn;
			len -= mn << 1;
		}
	}
	return ans + len / 3 * 2;
}

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