Submission #1203665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203665		aigorm	Mutating DNA (IOI21_dna)	C++20	0 / 100	30 ms	11244 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;
vector<pref> pref_tbl;

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

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

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

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

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

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

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

	if (abc[x][0] - abc[y][0] != 0 || abc[x][1] - abc[y][1] != 0 || abc[x][2] - abc[y][2] != 0) // 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: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16