Submission #1195721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195721		belgianbot	Mutating DNA (IOI21_dna)	C++20	0 / 100	59 ms	21548 KiB

dna

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

vector<vector<vector<int>>> pref;
map<char, int> mp;
int n;
void init(std::string a, std::string b) {
	n = a.size();
	pref.resize(a.size(), vector<vector<int>>(3, vector<int>(3,0)));
	mp['T'] = 0; mp['A'] = 1; mp['C'] = 2;

	for (int i = 0; i < a.size(); i++) {
		if (i) pref[i] = pref[i-1];
		pref[i][mp[a[i]]][mp[b[i]]]++;
	}
}

int get_distance(int x, int y) {
	int res = 0;
	vector<vector<int>> vec = {{0,0,0},{0,0,0},{0,0,0}};
	if (x) vec = pref[x-1];
	auto vec2 = pref[y];

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) vec2[i][j] -= vec[i][j];
	}
	for (int i = 0; i < 3; i++) {
		if (vec2[i][0] + vec2[i][1] + vec2[i][2] != vec2[0][i] + vec2[1][i] + vec2[2][i]) return -1;
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) continue;
			int mini = min(vec2[i][j], vec2[j][i]);
			res += mini;
			vec2[i][j] -= mini;
			vec2[j][i] -= mini;
		}
	}
	
	res += (y-x+1 - res * 2) / 3 * 2;
	return res;
}

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