Submission #996934

#	Time	Username	Problem	Language	Result	Execution time	Memory
996934		overwatch9	Mutating DNA (IOI21_dna)	C++17	100 / 100	86 ms	8444 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map <char, vector <int>> pfxa, pfxb;
map <string, vector <int>> pfx;
int n;
vector <char> tp = {'A', 'T', 'C'};
vector <string> tp2 = {"AC", "CA", "TA", "AT", "CT", "TC"};
void init(std::string a, std::string b) {
	n = a.size();
	for (auto i : tp)
		pfxa[i] = pfxb[i] = vector <int> (n+5);
	for (auto i : tp2)
		pfx[i] = vector <int> (n + 5);
	for (int i = 0; i < n; i++) {
		pfxa[a[i]][i]++;
		pfxb[b[i]][i]++;
		string tp3; tp3.resize(2);
		tp3[0] = a[i]; tp3[1] = b[i];
		if (a[i] != b[i])
			pfx[tp3][i]++;
		if (i > 0) {
			for (auto j : tp) {
				pfxa[j][i] += pfxa[j][i-1];
				pfxb[j][i] += pfxb[j][i-1];
			}
			for (auto j : tp2) {
				pfx[j][i] += pfx[j][i-1];
			}
		}
	}
}
int get_distance(int x, int y) {
	for (auto i : tp) {
		int s1 = pfxa[i][y];
		int s2 = pfxb[i][y];
		if (x > 0) {
			s1 -= pfxa[i][x-1];
			s2 -= pfxb[i][x-1];
		}
		if (s1 != s2)
			return -1;
	}
	int ans = 0;
	int cnt = pfx["AC"][y];
	if (x > 0)
		cnt -= pfx["AC"][x-1];
	int cnt2 = pfx["CA"][y];
	if (x > 0)
		cnt2 -= pfx["CA"][x-1];
	ans += abs(cnt - cnt2) * 2;
	ans += min(cnt, cnt2);

	cnt = pfx["AT"][y];
	if (x > 0)
		cnt -= pfx["AT"][x-1];
	cnt2 = pfx["TA"][y];
	if (x > 0)
		cnt2 -= pfx["TA"][x-1];
	ans += min(cnt, cnt2);

	cnt = pfx["CT"][y];
	if (x > 0)
		cnt -= pfx["CT"][x-1];
	cnt2 = pfx["TC"][y];
	if (x > 0)
		cnt2 -= pfx["TC"][x-1];
	ans += min(cnt, cnt2);
	return ans;
}

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