Submission #1009955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009955		Unlucky	Mutating DNA (IOI21_dna)	C++17	100 / 100	107 ms	6592 KiB

dna

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

string a, b;
map<string, int[100000]> prefix;

void init(string a1, string b1) {
	a = a1;
	b = b1;
	int n = a.length();
	for (int i = 0; i < n; i++){
		prefix["ta"][i+1] = (a[i] == 'T' && b[i] == 'A') ? prefix["ta"][i] + 1 : prefix["ta"][i];
		prefix["at"][i+1] = (a[i] == 'A' && b[i] == 'T') ? prefix["at"][i] + 1 : prefix["at"][i];
		prefix["tc"][i+1] = (a[i] == 'T' && b[i] == 'C') ? prefix["tc"][i] + 1 : prefix["tc"][i];
		prefix["ct"][i+1] = (a[i] == 'C' && b[i] == 'T') ? prefix["ct"][i] + 1 : prefix["ct"][i];
		prefix["ac"][i+1] = (a[i] == 'A' && b[i] == 'C') ? prefix["ac"][i] + 1 : prefix["ac"][i];
		prefix["ca"][i+1] = (a[i] == 'C' && b[i] == 'A') ? prefix["ca"][i] + 1 : prefix["ca"][i];
	}
}

int get_distance(int x, int y) {
	x++;
	y++;
	int ta = prefix["ta"][y] - prefix["ta"][x-1];
	int at = prefix["at"][y] - prefix["at"][x-1];
	int tc = prefix["tc"][y] - prefix["tc"][x-1];
	int ct = prefix["ct"][y] - prefix["ct"][x-1];
	int ac = prefix["ac"][y] - prefix["ac"][x-1];
	int ca = prefix["ca"][y] - prefix["ca"][x-1];
	int ret = 0;
	int m = min(ta, at);
	ta -= m;
	at -= m;
	ret += m;
	m = min(tc, ct);
	tc -= m;
	ct -= m;
	ret += m;
	m = min(ac, ca);
	ac -= m;
	ca -= m;
	ret += m;
	if (ta != ac || ta != ct){
		return -1;
	} else {
		ret += 2*ta;
	}
	if (at != ca || at != tc){
		return -1;
	} else {
		ret += 2*at;
	}
	return ret;
}

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