Submission #508216

#	Time	Username	Problem	Language	Result	Execution time	Memory
508216		ITO	Mutating DNA (IOI21_dna)	C++17	100 / 100	54 ms	7404 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int n, pa[100001][3][3], ma[26];
void init(std::string a, std::string b) {
	n = a.length();
	ma['A' - 'A'] = 0, ma['C' - 'A'] = 1, ma['T' - 'A'] = 2;
	for (int j = 0; j < 9; j++) {
		pa[0][j / 3][j % 3] = 0;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 9; j++) {
			pa[i + 1][j / 3][j % 3] = pa[i][j / 3][j % 3];
		}
		pa[i + 1][ma[a[i] - 'A']][ma[b[i] - 'A']]++;
	}
}

int get_distance(int x, int y) {
	int ar[3][3], c = 0;
	for (int i = 0; i < 9; i++) {
		ar[i / 3][i % 3] = pa[y + 1][i / 3][i % 3] - pa[x][i / 3][i % 3];
	}
	for (int i = 0; i < 3; i++) {
		int t = min(ar[i][(i + 1) % 3], ar[(i + 1) % 3][i]);
		c += t;
		ar[i][(i + 1) % 3] -= t, ar[(i + 1) % 3][i] -= t;
	}
	if (ar[0][1] != ar[1][2] || ar[1][2] != ar[2][0] || ar[1][0] != ar[2][1] || ar[2][1] != ar[0][2]) {
		return -1;
	}
	return c + (ar[0][1] + ar[1][0]) * 2;
}

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