Submission #935148

#	Time	Username	Problem	Language	Result	Execution time	Memory
935148		jerzyk	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	9744 KiB

dna

#include <bits/stdc++.h>

using namespace std;
const int N = 100 * 1000 + 7;
int sum[2][3][N], ilz[3][3][N];

int Num(char z)
{
	if(z == 'A')
		return 0;
	if(z == 'T')
		return 1;
	return 2;
}

int get_distance(int x, int y)
{
	int w, i, j, p, k, d;
	p = x + 1;
	k = y + 1;
	w = 0;
	d = k - p + 1;
	for(i = 0; i < 3; ++i)
		if(sum[0][i][k] - sum[0][i][p - 1] != sum[1][i][k] - sum[1][i][p - 1])
			return -1;
	for(i = 0; i < 3; ++i)
	{
		for(j = 0; j <= i; ++j)
		{
			if(i == j)
			{
				d -= min(ilz[i][j][k] - ilz[i][j][p - 1], ilz[j][i][k] - ilz[j][i][p - 1]);
			}
			else
			{
				d -= 2 * min(ilz[i][j][k] - ilz[i][j][p - 1], ilz[j][i][k] - ilz[j][i][p - 1]);
				w += min(ilz[i][j][k] - ilz[i][j][p - 1], ilz[j][i][k] - ilz[j][i][p - 1]);
			}
		}
	}
	return w + (d * 2 / 3);
}

void init(string a, string b)
{
	int i, k, j, n1, n2;
	for(i = 1; i <= (int)a.size(); ++i)
	{
		n1 = Num(a[i - 1]);
		n2 = Num(b[i - 1]);
		++sum[0][n1][i];
		++sum[1][n2][i];
		++ilz[n1][n2][i];
		for(j = 0; j < 3; ++j)
		{
			sum[0][j][i] += sum[0][j][i - 1];
			sum[1][j][i] += sum[1][j][i - 1];
		}
		for(j = 0; j < 3; ++j)
			for(k = 0; k < 3; ++k)
				ilz[j][k][i] += ilz[j][k][i - 1];
	}
}

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