Submission #1179789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179789		madamadam3	Mutating DNA (IOI21_dna)	C++20	35 / 100	25 ms	7496 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
const int MAXN = 100'001;

int n;
string A, B;

int prefixA[3][MAXN];
int prefixB[3][MAXN];
int prefixDiff[6][MAXN]; // pd[0]: A, T, pd[1]: A, C, pd[2]: T, A, pd[3]: T, C, pd[4]: C, A, pd[5]: C, T

int gi(char inp) {
	if (inp == 'A') return 0;
	else if (inp == 'T') return 1;
	else return 2;
}

char g(int i) {
	if (i == 0) return 'A';
	else if (i == 1) return 'T';
	else return 'G';
}

int p(int i, int j) {
	if (i == 0 && j == 1) return 0;
	else if (i == 0 && j == 2) return 1;
	else if (i == 1 && j == 0) return 2;
	else if (i == 1 && j == 2) return 3;
	else if (i == 2 && j == 1) return 4;
	else return 5;
}
 
void init(string a, string b) {
	A = a;
	B = b;
	n = (int) a.size();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			prefixA[j][i + 1] = prefixA[j][i];
			prefixB[j][i + 1] = prefixB[j][i];
		}

		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				int is_diff = (a[i] == g(j) && b[i] == g(k)) ? 1 : 0;
				prefixDiff[p(j, k)][i+1] = prefixDiff[p(j, k)][i] + is_diff; 
			}
		}

		prefixA[gi(a[i])][i+1]++;
		prefixB[gi(b[i])][i+1]++;
	}
}


int get_distance(int x, int y) {
	for (int j = 0; j < 3; j++) {
		int cntA = prefixA[j][y + 1] - prefixA[j][x];
		int cntB = prefixB[j][y + 1] - prefixB[j][x];

		if (cntA != cntB) return -1;
	}

	return prefixDiff[p(0, 1)][y + 1] - prefixDiff[p(0, 1)][x];	
}

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