Submission #1085123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085123		acoatoitgs	Mutating DNA (IOI21_dna)	C++17	56 / 100	28 ms	6248 KiB

dna

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

int N;
vector<array<int, 3>> A, B;
int c(char a)
{
	return (a == 'A' ? 0 : (a == 'T' ? 1 : 2));
}
void init(std::string a, std::string b)
{
	N = a.size();
	A.resize(N, {0, 0, 0});
	B.resize(N, {0, 0, 0});

	if (a[0] != b[0])
	{
		A[0][c(a[0])]++;
		B[0][c(b[0])]++;
	}
	for (int i = 1; i < N; i++)
	{
		A[i][0] = A[i - 1][0];
		A[i][1] = A[i - 1][1];
		A[i][2] = A[i - 1][2];

		B[i][0] = B[i - 1][0];
		B[i][1] = B[i - 1][1];
		B[i][2] = B[i - 1][2];

		if (a[i] != b[i])
		{
			A[i][c(a[i])]++;
			B[i][c(b[i])]++;
		}
	}
}

int get_distance(int x, int y)
{
	array<int, 3> dA = A[y], dB = B[y];

	if (x != 0)
	{
		dA[0] -= A[x - 1][0];
		dA[1] -= A[x - 1][1];
		dA[2] -= A[x - 1][2];

		dB[0] -= B[x - 1][0];
		dB[1] -= B[x - 1][1];
		dB[2] -= B[x - 1][2];
	}

	if (dA == dB)
	{
		return (1 + dA[0] + dA[1] + dA[2]) / 2;
	}

	return -1;
}

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