Submission #576053

#	Time	Username	Problem	Language	Result	Execution time	Memory
576053		KrisjanisP	Mutating DNA (IOI21_dna)	C++17	56 / 100	57 ms	10880 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MX_N = 1e5;

ll ps[3][3][MX_N]; // ATC
void init(std::string a, std::string b) {
	ll n = a.size();
	for(ll i=0;i<n;i++)
	{
		ll av,bv;
		if(a[i]=='A') av=0;
		else if(a[i]=='T') av=1;
		else av=2;
		if(b[i]=='A') bv=0;
		else if(b[i]=='T') bv=1;
		else bv=2;
		ps[av][bv][i]++;
		if(i)
		{
			for(ll j=0;j<3;j++)
			{
				for(ll k=0;k<3;k++)
				{
					ps[j][k][i]+=ps[j][k][i-1];
				}
			}
		}
	}
}

int get_distance(int x, int y) {
	ll matrix[3][3];
	for(ll i=0;i<3;i++)
	{
		for(ll j=0;j<3;j++)
		{
			matrix[i][j] = ps[i][j][y];
			if(x)
				matrix[i][j] -= ps[i][j][x-1];
		}
	}
	ll cnt[2][3];
	for(ll i=0;i<2;i++)
		for(ll j=0;j<3;j++)
			cnt[i][j]=0;
	for(ll i=0;i<3;i++)
	{
		for(ll j=0;j<3;j++)
		{
			cnt[0][i] += matrix[i][j];
			cnt[1][j] += matrix[i][j];
		}
	}
	for(ll i=0;i<3;i++)
		if(cnt[0][i]!=cnt[1][i])
			return -1;
	ll res[2] = {}; // swaping, permuting
	for(ll i=0;i<3;i++)
	{
		for(ll j=i+1;j<3;j++)
		{
			ll mn = min(matrix[i][j],matrix[j][i]);
			ll mx = max(matrix[i][j],matrix[j][i]);
			res[0] += mn;
			res[1] += mx-mn;
		}
	}
	return res[0]+max(0ll,res[1]-1);
}

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