Submission #672009

#	Time	Username	Problem	Language	Result	Execution time	Memory
672009		speedyArda	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	7408 KiB

dna

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

using namespace std;
int letters[100005][3][3];
pair< pair<int, int>, int> changes[6] = {{{0, 1}, 2}, {{0, 2}, 1}, {{1, 0}, 2}, {{1, 2}, 0}, {{2, 0}, 1}, {{2, 1}, 0}};
void init(string a, string b) {
	int n = a.size();
	for(int i = 0; i < n; i++)
	{
		if(i > 0)
		{
			for(int l = 0; l < 3; l++)
				for(int k = 0; k < 3; k++)
					letters[i][l][k] = letters[i - 1][l][k];
		}
		if(a[i] == 'T')
			a[i] = 'B';
		if(b[i] == 'T')
			b[i] = 'B';
		letters[i][a[i] - 'A'][b[i] - 'A']++;
		//cout << i << "\n";
	}

}

int get_distance(int x, int y) {
	int temp[3][3];
	for(int i = 0; i < 3; i++) {
		for(int l = 0; l < 3; l++) {
			temp[i][l] = letters[y][i][l];
		}
	}

	if(x != 0)
	{
		for(int i = 0; i < 3; i++) {
			for(int l = 0; l < 3; l++) {
				temp[i][l] -= letters[x - 1][i][l];
			}
		}
	}

	long long res = 0;
	for(int i = 0; i < 3; i++)
	{
		for(int l = 0; l < 3; l++)
		{
			if(i == l)
				continue;
			long long val = min(temp[i][l], temp[l][i]);
			res += val;
			temp[i][l] -= val;
			temp[l][i] -= val;
			temp[i][i] += val;
			temp[l][l] += val;
		}
	}
	//cout << temp[0][0] << " " << temp[1][1] << " " << temp[2][2]<< "\n";
	for(int i = 0; i < 3; i++)
	{
		for(int l = 0; l < 3; l++)
		{
			if(i == l)
				continue;
			int oth = 3 - i - l;
			long long val = min(temp[i][oth], temp[l][i]);
			res += val;
			temp[i][oth] -= val;
			temp[l][i] -= val;
			temp[i][i] += val;
			temp[l][oth] += val;
			val = min(temp[l][oth], temp[oth][l]);
			res += val;
			temp[oth][l] -= val;
			temp[l][oth] -= val;
			temp[oth][oth] += val;
			temp[l][l] += val;
		}
	}

	int curr = temp[0][0] + temp[1][1] + temp[2][2];
	//cout << curr << " " << temp[0][0] << " " << temp[1][1] << " " << temp[2][2]<< "\n";
	if(curr != y - x + 1)
		res = -1;
	return res;
}

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