Submission #753722

#	Time	Username	Problem	Language	Result	Execution time	Memory
753722		nicksms	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	7628 KiB

dna

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

string A, B;
V<V<vi>> cnts(3,V<vi>(3));

void init(string a, string b) {
	A=a, B=b;
	map<char, int> m = {{'A',0}, {'T',1}, {'C',2}};
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
		cnts[i][j]=vi(sz(a)+1);
	}
	for (int i = 0; i < sz(a); i++) {
		cnts[m[a[i]]][m[b[i]]][i+1] = 1;
	}
	for (int i = 0; i < 3; i++) 
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < sz(a); k++) 
				cnts[i][j][k+1] += cnts[i][j][k];
}

int get_distance(int x, int y) {
	vi t(3); 
	V<vi> e(3,vi(3));
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			t[i] += (e[i][j] = cnts[i][j][y+1]-cnts[i][j][x]);
			t[j] -= e[i][j];
		}
	}
	for (int i = 0; i < 3; i++) if (t[i]) return -1;
	int tot = 0;
	for (int i = 0; i < 3; i++) 
		for (int j = 0; j < 3; j++) if (i != j) {
			int m = min(e[i][j],e[j][i]);
			tot += m; e[i][j] -= m; e[j][i] -= m;
		}
	int rem = 0;
	for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) rem += e[i][j];
	assert(rem % 3 == 0);
	return tot + 2*(rem/3);
}

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