Submission #778310

#	Time	Username	Problem	Language	Result	Execution time	Memory
778310		Minindu206	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	8584 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int aA[MAXN], aT[MAXN], aC[MAXN], bA[MAXN], bT[MAXN], bC[MAXN], AT[MAXN], TA[MAXN], AC[MAXN], CA[MAXN], CT[MAXN], TC[MAXN];
void init(string a, string b)
{
	int n = a.size();
	for (int i = 0; i < n; i++)
	{
		aA[i + 1] = aA[i];
		aT[i + 1] = aT[i];
		aC[i + 1] = aC[i];
		bA[i + 1] = bA[i];
		bT[i + 1] = bT[i];
		bC[i + 1] = bC[i];
		AT[i + 1] = AT[i];
		TA[i + 1] = TA[i];
		AC[i + 1] = AC[i];
		CA[i + 1] = CA[i];
		CT[i + 1] = CT[i];
		TC[i + 1] = TC[i];
		if (a[i] == 'A')
			aA[i + 1]++;
		else if (a[i] == 'C')
			aC[i + 1]++;
		else
			aT[i + 1]++;

		if (b[i] == 'A')
			bA[i + 1]++;
		else if (b[i] == 'C')
			bC[i + 1]++;
		else
			bT[i + 1]++;

		if (a[i] == 'A' && b[i] == 'T')
			AT[i + 1]++;
		if (a[i] == 'T' && b[i] == 'A')
			TA[i + 1]++;
		if (a[i] == 'C' && b[i] == 'T')
			CT[i + 1]++;
		if (a[i] == 'T' && b[i] == 'C')
			TC[i + 1]++;
		if (a[i] == 'A' && b[i] == 'C')
			AC[i + 1]++;
		if (a[i] == 'C' && b[i] == 'A')
			CA[i + 1]++;
	}
}

int get_distance(int x, int y)
{
	x++, y++;
	if (!((aA[y] - aA[x - 1] == bA[y] - bA[x - 1]) && (aC[y] - aC[x - 1] == bC[y] - bC[x - 1]) && (aT[y] - aT[x - 1] == bT[y] - bT[x - 1])))
		return -1;
	int a1 = AT[y] - AT[x - 1];
	int a2 = TA[y] - TA[x - 1];
	int a3 = AC[y] - AC[x - 1];
	int a4 = CA[y] - CA[x - 1];
	int a5 = CT[y] - CT[x - 1];
	int a6 = TC[y] - TC[x - 1];
	return min(a1,a2) + min(a3,a4) + min(a5,a6) + ((abs(a1 - a2) + abs(a3 - a4) + abs(a5 - a6)) / 3) * 2;
}

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