Submission #446617

#	Time	Username	Problem	Language	Result	Execution time	Memory
446617		tkwiatkowski	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	9728 KiB

dna

/*
	Zadanie: Mutating DNA
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 1000*1000 + 7;
const int INF = 1000*1000*1000 + 7;

char toChar[3] = {'A', 'T', 'C'};
int cnt1[MAXN][3], cnt2[MAXN][3];
int pref[MAXN][3][3];

void init(string a, string b)
{
	int n = a.size();
	for (int i = 1; i <= n; ++i) {
		for (int c1 = 0; c1 < 3; ++c1) {
			cnt1[i][c1] = cnt1[i - 1][c1];
			cnt2[i][c1] = cnt2[i - 1][c1];
			if (a[i - 1] == toChar[c1])
				++cnt1[i][c1];
			if (b[i - 1] == toChar[c1])
				++cnt2[i][c1];

			for (int c2 = 0; c2 < 3; ++c2) {
				pref[i][c1][c2] = pref[i - 1][c1][c2];
				if (a[i - 1] == toChar[c1] && b[i - 1] == toChar[c2]) {
					++pref[i][c1][c2];
				}
			}
		}
	}
}

int get_distance(int x, int y)
{
	++x, ++y;

	for (int c = 0; c < 3; ++c) {
		if ((cnt1[y][c] - cnt1[x - 1][c]) != (cnt2[y][c] - cnt2[x - 1][c])) {
			return -1;
		}
	}

	int tmp[3][3];
	for (int c1 = 0; c1 < 3; ++c1) {
		for (int c2 = 0; c2 < 3; ++c2) {
			tmp[c1][c2] = pref[y][c1][c2] - pref[x - 1][c1][c2];
		}
	}

	int res = 0;
	int minn = min(tmp[0][1], tmp[1][0]);
	tmp[0][1] -= minn;
	tmp[1][0] -= minn;
	res += minn;
	minn = min(tmp[0][2], tmp[2][0]);
	tmp[0][2] -= minn;
	tmp[2][0] -= minn;
	res += minn;
	minn = min(tmp[2][1], tmp[1][2]);
	tmp[2][1] -= minn;
	tmp[1][2] -= minn;
	res += minn;

	int sum = 0, maxx = 0;
	for (int c1 = 0; c1 < 3; ++c1) {
		for (int c2 = 0; c2 < 3; ++c2) {
			if (c1 == c2)
				continue;
			sum += tmp[c1][c2];
			maxx = max(tmp[c1][c2], maxx);
		}
	}

	res += (sum - maxx);

	return res;
}

/*int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, q;
	cin >> n >> q;
	string s1, s2;
	cin >> s1 >> s2;
	init(s1, s2);
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << get_distance(x, y) << '\n';
	}

	return 0;
}*/

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