Submission #493599

#	Time	Username	Problem	Language	Result	Execution time	Memory
493599		TranGiaHuy1508	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	8880 KiB

dna

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

typedef vector<int> vi;

int cv(char c){
	if (c == 'A') return 0;
	if (c == 'T') return 1;
	return 2;
}

vi pfxa[3], pfxb[3];
vi pfx[6];

int n;
string a, b;

void init(string A, string B){
	a = A; b = B;

	n = a.length();

	for (int i=0; i<3; i++) pfxa[i].assign(n, 0);
	for (int i=0; i<3; i++) pfxb[i].assign(n, 0);
	for (int i=0; i<6; i++) pfx[i].assign(n, 0);

	for (int i=0; i<n; i++){
		for (int j=0; j<3; j++){
			pfxa[j][i] = (i == 0 ? 0 : pfxa[j][i-1]) + (j == cv(a[i]));
		}
	}

	for (int i=0; i<n; i++){
		for (int j=0; j<3; j++){
			pfxb[j][i] = (i == 0 ? 0 : pfxb[j][i-1]) + (j == cv(b[i]));
		}
	}

	for (int i=0; i<n; i++){
		for (int j=0; j<6; j++){
			pfx[j][i] = (i == 0 ? 0 : pfx[j][i-1]);
		}
		if (a[i] == 'A' && b[i] == 'T') pfx[0][i]++;
		if (a[i] == 'T' && b[i] == 'A') pfx[1][i]++;
		if (a[i] == 'A' && b[i] == 'C') pfx[2][i]++;
		if (a[i] == 'C' && b[i] == 'A') pfx[3][i]++;
		if (a[i] == 'T' && b[i] == 'C') pfx[4][i]++;
		if (a[i] == 'C' && b[i] == 'T') pfx[5][i]++;
	}
}

int get_distance(int x, int y){
	if (x == 0){
		if (pfxa[0][y] != pfxb[0][y]){
			return -1;
		}
		if (pfxa[1][y] != pfxb[1][y]){
			return -1;
		}
		if (pfxa[2][y] != pfxb[2][y]){
			return -1;
		}
	}
	else{
		if ((pfxa[0][y] - pfxa[0][x-1]) != (pfxb[0][y] - pfxb[0][x-1])){
			return -1;
		}
		if ((pfxa[1][y] - pfxa[1][x-1]) != (pfxb[1][y] - pfxb[1][x-1])){
			return -1;
		}
		if ((pfxa[2][y] - pfxa[2][x-1]) != (pfxb[2][y] - pfxb[2][x-1])){
			return -1;
		}
	}

	int ca = pfx[0][y] - (x == 0 ? 0 : pfx[0][x-1]);
	int cb = pfx[1][y] - (x == 0 ? 0 : pfx[1][x-1]);
	int cc = pfx[2][y] - (x == 0 ? 0 : pfx[2][x-1]);
	int cd = pfx[3][y] - (x == 0 ? 0 : pfx[3][x-1]);
	int ce = pfx[4][y] - (x == 0 ? 0 : pfx[4][x-1]);
	int cf = pfx[5][y] - (x == 0 ? 0 : pfx[5][x-1]);
	
	int res = 0;

	int m1 = min(ca, cb), m2 = min(cc, cd), m3 = min(ce, cf);

	res += m1 + m2 + m3;
	ca -= m1; cb -= m1;
	cc -= m2; cd -= m2;
	ce -= m3; cf -= m3;

	res += 2 * (ca + cb);

	return res;
}

#ifdef LOCAL

int main(){
	string A, B; cin >> A >> B;
	init(A, B);

	int q; cin >> q;
	for (int i=0; i<q; i++){
		int x, y; cin >> x >> y;
		cout << get_distance(x, y) << "\n";
	}
}

#endif

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