Submission #1203679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203679		aigorm	Mutating DNA (IOI21_dna)	C++20	71 / 100	1597 ms	12788 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
// #include </home/igor/cpp-dump/cpp-dump.hpp>
#define pb push_back
#define ll long long
using namespace std;

// A => 0
// C => 1
// T => 2

vector<int> A, B;

typedef vector<array<int, 3>> pref;

pref abc[2];
vector<pref> pref_tbl;

void init(string a, string b)
{
	// cerr << "A\n";
	//  adder.clear();
	//              A  C  T
	array<int, 3> fs = {0, 0, 0};
	array<int, 3> sc = {0, 0, 0};
	pref adder = {{0, 0, 0},
				  {0, 0, 0},
				  {0, 0, 0}};
	pref_tbl.clear();
	abc[0].clear();
	abc[1].clear();
	A.clear();
	B.clear();
	pref_tbl.pb(adder);
	abc[0].pb(fs);
	abc[1].pb(sc);

	for (int i = 0; i < a.size(); i++)
	{
		if (b[i] == 'A')
		{
			B.pb(0);
			fs[0]++;
		}
		else if (b[i] == 'C')
		{
			B.pb(1);
			fs[1]++;
		}
		else if (b[i] == 'T')
		{
			B.pb(2);
			fs[2]++;
		}

		// cpp_dump(adder);
		// cpp_dump(pref_tbl);
		if (a[i] == 'A')
		{
			A.pb(0);
			sc[0]++;

			if (b[i] == 'C')
				adder[0][1]++;
			if (b[i] == 'T')
				adder[0][2]++;
		}
		else if (a[i] == 'C')
		{
			A.pb(1);
			sc[1]++;

			if (b[i] == 'A')
				adder[1][0]++;
			if (b[i] == 'T')
				adder[1][2]++;
		}
		else if (a[i] == 'T')
		{
			A.pb(2);
			sc[2]++;

			if (b[i] == 'A')
				adder[2][0]++;
			if (b[i] == 'C')
				adder[2][1]++;
		}
		pref_tbl.pb(adder);
		abc[0].pb(fs);
		abc[1].pb(sc);
	}
}

int get_distance(int x, int y)
{
	// cerr << "D\n";

	// cpp_dump(abc);
	if (abc[0][y + 1][0] - abc[0][x][0] != abc[1][y + 1][0] - abc[1][x][0] ||
		abc[0][y + 1][1] - abc[0][x][1] != abc[1][y + 1][1] - abc[1][x][1] ||
		abc[0][y + 1][2] - abc[0][x][2] != abc[1][y + 1][2] - abc[1][x][2]) // literki się nie nakładają
		return -1;

	// cerr << "C\n";

	// cpp_dump(pref_tbl);

	int ans = 0;

	pref curr = pref_tbl[y + 1];
	// cerr << "D'\n";

	curr[0][1] -= pref_tbl[x][0][1];
	curr[0][2] -= pref_tbl[x][0][2];
	// cerr << "D''\n";

	curr[1][0] -= pref_tbl[x][1][0];
	curr[1][2] -= pref_tbl[x][1][2];
	// cerr << "D'''\n";

	curr[2][0] -= pref_tbl[x][2][0];
	curr[2][1] -= pref_tbl[x][2][1];

	// cerr << "E\n";
	for (int i = x; i <= y; i++)
	{
		// cerr << "F\n";

		// cpp_dump(curr);
		// cpp_dump(i, A[i], B[i]);
		// cpp_dump(curr[A[i]][B[i]], curr[B[i]][A[i]]);

		if (A[i] == B[i])
			continue;

		if (curr[A[i]][B[i]] == 0 && curr[B[i]][A[i]] == 0) // oba już zamienione
			continue;

		if (curr[A[i]][B[i]] > 0 && curr[B[i]][A[i]] > 0) // oba możemy zamienić miejscami
		{
			ans++;
			curr[A[i]][B[i]]--;
			curr[B[i]][A[i]]--;
			continue;
		}

		int trzeci;
		if (A[i] != 0 && B[i] != 0)
			trzeci = 0;
		else if (A[i] != 1 && B[i] != 1)
			trzeci = 1;
		else if (A[i] != 2 && B[i] != 2)
			trzeci = 2;

		if (curr[A[i]][B[i]] > 0) // A na B ale nie B na A
		{
			curr[A[i]][trzeci]++;
			curr[A[i]][B[i]]--;
			curr[B[i]][trzeci]--;
			ans++;
			continue;
		}
		else if (curr[A[i]][B[i]] > 0) // A na B ale nie B na A
		{
			curr[B[i]][trzeci]++;
			curr[B[i]][A[i]]--;
			curr[A[i]][trzeci]--;
			ans++;
			continue;
		}
		else
			cerr << "error0\n";
	}
	// cerr << "G\n";
	return ans;
}

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