Submission #1318665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318665		nikaa123	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	7296 KiB

dna

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

const int N = 2e5+5;

int n;
int prefaa[N],prefat[N],prefac[N],prefba[N],prefbt[N],prefbc[N];
int prefAT[N],prefTA[N],prefAC[N],prefCA[N],prefTC[N],prefCT[N];

void init(string a, string b) {
	n = a.size();
	a = " " + a;
	b = " " + b;
	for (int i = 1; i <= n; i++) {
		prefaa[i] = prefaa[i-1] + (a[i] == 'A');
		prefat[i] = prefat[i-1] + (a[i] == 'T');
		prefac[i] = prefac[i-1] + (a[i] == 'C');

		prefba[i] = prefba[i-1] + (b[i] == 'A');
		prefbt[i] = prefbt[i-1] + (b[i] == 'T');
		prefbc[i] = prefbc[i-1] + (b[i] == 'C');
	}

	for (int i = 1; i <= n ; i++) {
		prefAT[i] = prefAT[i-1] + (a[i] == 'A' && b[i] == 'T');
		prefTA[i] = prefTA[i-1] + (a[i] == 'T' && b[i] == 'A');

		prefAC[i] = prefAC[i-1] + (a[i] == 'A' && b[i] == 'C');
		prefCA[i] = prefCA[i-1] + (a[i] == 'C' && b[i] == 'A');

		prefCT[i] = prefCT[i-1] + (a[i] == 'C' && b[i] == 'T');
		prefTC[i] = prefTC[i-1] + (a[i] == 'T' && b[i] == 'C');
	}

}

int get_distance(int x, int y) {
	y++;
	if (prefaa[y]-prefaa[x] != prefba[y]-prefba[x]) return -1;
	if (prefat[y]-prefat[x] != prefbt[y]-prefbt[x]) return -1;
	if (prefac[y]-prefac[x] != prefbc[y]-prefbc[x]) return -1;
	
	int at = prefAT[y]-prefAT[x];
	int ta = prefTA[y]-prefTA[x];

	int ac = prefAC[y]-prefAC[x];
	int ca = prefCA[y]-prefCA[x];

	int ct = prefCT[y]-prefCT[x];
	int tc = prefTC[y]-prefTC[x];

	int mn1 = min(at,ta);
	int mn2 = min(ac,ca);
	int mn3 = min(ct,tc);

	int ans = 0;
	ans += (mn1 + mn2 + mn3);
	at -= mn1; ta -= mn1;
	ac -= mn2; ca -= mn2;
	ct -= mn3; tc -= mn3;
	ans += 2*max(at,ta);

	return ans;
}

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