Submission #1003705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003705		coolboy19521	Mutating DNA (IOI21_dna)	C++17	100 / 100	31 ms	7780 KiB

dna

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

using namespace std;

const int sz = 1e5 + 5;

map<char, int> en;
int p[sz][3][3];
int n;

string s, t;

void init(string a, string b) {
	n = a.size();
	s = ' ' + a, t = ' ' + b;

	en['A'] = 0, en['T'] = 1, en['C'] = 2;

	for (int i = 1; i <= n; i ++) {
		if (s[i] != t[i]) {
			int a = en[s[i]];
			int b = en[t[i]];
			p[i][a][b] ++;
		}

		for (int j = 0; j < 3; j ++) {
			for (int k = 0; k < 3; k ++) {
				p[i][j][k] += p[i - 1][j][k];
			}
		}
	}
}

int get_distance(int x, int y) {
	x ++, y  ++;
	bool v[3][3] {};
	int cn[3] {};
	int d = 0;
	for (int i = 0; i < 3; i ++) {
		for (int j = 0; j < 3; j ++) {
			int cni = p[y][i][j] - p[x - 1][i][j];
			int cnj = p[y][j][i] - p[x - 1][j][i];
			if (cni >= cnj && !v[j][i]) {
				cn[i] += cni - cnj;
				v[i][j] = true;
				d += cnj;
			}
		}
	}
	if (cn[0] == cn[1] && cn[1] == cn[2]) {
		d += cn[0] * 2;
	} else {
		return -1;
	}

	return d;
}

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