Submission #437095

#	Time	Username	Problem	Language	Result	Execution time	Memory
437095		tutis	Mutating DNA (IOI21_dna)	C++17	100 / 100	72 ms	6096 KiB

dna

#include "dna.h"
int C[3][3][100001];
void init(std::string a, std::string b) {
	int n = a.size();
	for (int i = 0; i < n; i++)
	{
		for (int x = 0; x < 3; x++)
			for (int y = 0; y < 3; y++)
				C[x][y][i + 1] = C[x][y][i];
		int c1 = 0;
		int c2 = 0;
		if (a[i] == 'A')
			c1 = 1;
		if (a[i] == 'T')
			c1 = 2;
		if (b[i] == 'A')
			c2 = 1;
		if (b[i] == 'T')
			c2 = 2;
		C[c1][c2][i + 1]++;
	}
}
#include <bits/stdc++.h>
using namespace std;
int get_distance(int x, int y) {
	int A[3][3];
	for (int a = 0; a < 3; a++)
	{
		for (int b = 0; b < 3; b++)
		{
			A[a][b] = C[a][b][y + 1] - C[a][b][x];
		}
	}
	for (int a = 0; a < 3; a++)
	{
		int bal = 0;
		for (int b = 0; b < 3; b++)
		{
			bal += A[a][b];
			bal -= A[b][a];
		}
		if (bal != 0)
			return -1;
	}
	int ans = 0;
	bool ok = true;
	while (ok)
	{
		ok = false;
		for (int x : {0, 1, 2})
		{
			for (int y : {0, 1, 2})
			{
				if (x == y)
					continue;
				int c = min({A[x][y], A[y][x]});
				A[x][y] -= c;
				A[y][x] -= c;
				ans += c;
				if (c != 0)
					ok = true;
			}
		}
		for (int x : {0, 1, 2})
		{
			for (int y : {0, 1, 2})
			{
				if (x == y)
					continue;
				int z = 3 - x - y;
				int c = min({A[x][y], A[y][z], A[z][x]});
				A[x][y] -= c;
				A[y][z] -= c;
				A[z][x] -= c;
				ans += 2 * c;
				if (c != 0)
					ok = true;
			}
		}
	}
	return ans;
}

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