Submission #1010476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010476		induwara16	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	8916 KiB

dna

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

typedef string str;
typedef vector<int> vi;

str a, b;
vi ac, at, ca, ct, ta, tc, as1, cs1, ts1, as2, cs2, ts2;

void init(str a1, str b1)
{
	a = a1;
	b = b1;

	int n = a.length();

	ac = vi(n);
	at = vi(n);
	ca = vi(n);
	at = vi(n);
	ta = vi(n);
	tc = vi(n);
	ct = vi(n);
	as1 = vi(n);
	cs1 = vi(n);
	ts1 = vi(n);
	as2 = vi(n);
	cs2 = vi(n);
	ts2 = vi(n);

	int ac_ = 0,
		at_ = 0,
		ca_ = 0,
		ta_ = 0,
		tc_ = 0,
		ct_ = 0,
		as1_ = 0,
		cs1_ = 0,
		ts1_ = 0,
		as2_ = 0,
		cs2_ = 0,
		ts2_ = 0;

	for (int i = 0; i < n; i++)
	{
		switch (b[i])
		{
		case 'A':
			as2_++;
			as2[i] = as2_;
			cs2[i] = cs2_;
			ts2[i] = ts2_;
			break;
		case 'C':
			cs2_++;
			as2[i] = as2_;
			cs2[i] = cs2_;
			ts2[i] = ts2_;
			break;
		case 'T':
			ts2_++;
			as2[i] = as2_;
			cs2[i] = cs2_;
			ts2[i] = ts2_;
			break;
		}
		switch (a[i])
		{
		case 'A':
			as1_++;
			as1[i] = as1_;
			cs1[i] = cs1_;
			ts1[i] = ts1_;

			if (b[i] == 'C')
				ac_++;
			else if (b[i] == 'T')
				at_++;

			ac[i] = ac_;
			at[i] = at_;
			ca[i] = ca_;
			ct[i] = ct_;
			tc[i] = tc_;
			ta[i] = ta_;
			break;
		case 'C':
			cs1_++;
			as1[i] = as1_;
			cs1[i] = cs1_;
			ts1[i] = ts1_;

			if (b[i] == 'A')
				ca_++;
			else if (b[i] == 'T')
				ct_++;

			ac[i] = ac_;
			at[i] = at_;
			ca[i] = ca_;
			ct[i] = ct_;
			tc[i] = tc_;
			ta[i] = ta_;
			break;
		case 'T':
			ts1_++;
			as1[i] = as1_;
			cs1[i] = cs1_;
			ts1[i] = ts1_;

			if (b[i] == 'C')
				tc_++;
			else if (b[i] == 'A')
				ta_++;

			ac[i] = ac_;
			at[i] = at_;
			ca[i] = ca_;
			ct[i] = ct_;
			tc[i] = tc_;
			ta[i] = ta_;

			break;
		}
	}
}

int get_distance(int x, int y)
{
	if (
		(as1[y] - (x == 0 ? 0 : as1[x - 1])) != (as2[y] - (x == 0 ? 0 : as2[x - 1])) ||
		(cs1[y] - (x == 0 ? 0 : cs1[x - 1])) != (cs2[y] - (x == 0 ? 0 : cs2[x - 1])) ||
		(ts1[y] - (x == 0 ? 0 : ts1[x - 1])) != (ts2[y] - (x == 0 ? 0 : ts2[x - 1])))
		return -1;

	int cntAC = ac[y] - (x == 0 ? 0 : ac[x - 1]);
	int cntAT = at[y] - (x == 0 ? 0 : at[x - 1]);
	int cntCA = ca[y] - (x == 0 ? 0 : ca[x - 1]);
	int cntCT = ct[y] - (x == 0 ? 0 : ct[x - 1]);
	int cntTA = ta[y] - (x == 0 ? 0 : ta[x - 1]);
	int cntTC = tc[y] - (x == 0 ? 0 : tc[x - 1]);

	int c = 0, m = cntAC + cntCA + cntAT + cntTA + cntTC + cntCT;

	m -= min(cntAC, cntCA) * 2;
	c += min(cntAC, cntCA);

	m -= min(cntAT, cntTA) * 2;
	c += min(cntAT, cntTA);

	m -= min(cntTC, cntCT) * 2;
	c += min(cntTC, cntCT);

	return m / 3 * 2 + c;
}

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