Submission #850248

#	Time	Username	Problem	Language	Result	Execution time	Memory
850248		StefanSebez	Mutating DNA (IOI21_dna)	C++17	100 / 100	119 ms	55316 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e5+50;
int a[N],b[N],n,pref[N][4][3];
map<pair<int,int>,int>pmapa[N];
void init(std::string s, std::string t)
{
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]==t[i-1])
		{
			a[i]=0,b[i]=0;
			continue;
		}
		if(s[i-1]=='A') a[i]=1;
		if(s[i-1]=='C') a[i]=2;
		if(s[i-1]=='T') a[i]=3;
		if(t[i-1]=='A') b[i]=1;
		if(t[i-1]=='C') b[i]=2;
		if(t[i-1]=='T') b[i]=3;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{
			for(int k=1;k<=2;k++)
			{
				pref[i][j][k]=pref[i-1][j][k];
			}
		}
		pref[i][a[i]][1]++;
		pref[i][b[i]][2]++;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{
			for(int k=1;k<=3;k++)
			{
				if(j==k)continue;
				pmapa[i][{j,k}]=pmapa[i-1][{j,k}];
			}
		}
		pmapa[i][{a[i],b[i]}]++;
		//if(a[i]==b[j] && a[j]==b[i]) par.push_back({i,j});
	}
}

int get_distance(int x, int y)
{
	x++,y++;
	int num[4][3],res=0;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=2;j++)
		{
			num[i][j]=pref[y][i][j]-pref[x-1][i][j];
			//printf("%i %i: %i\n",i,j,num[i][j]);
		}
	}
	for(int i=1;i<=3;i++)
	{
		if(num[i][1]!=num[i][2]) return -1;
	}
	for(int i=1;i<=3;i++)
	{
		for(int j=i+1;j<=3;j++)
		{
			int a=pmapa[y][{i,j}]-pmapa[x-1][{i,j}],b=pmapa[y][{j,i}]-pmapa[x-1][{j,i}];
			//printf("%i %i %i %i: %i %i\n",x,y,i,j,a,b);
			a=min(a,b);
			num[i][1]-=a;
			num[j][1]-=a;
			res+=a;
		}
	}
	/*for(auto i:par)
	{
		if(x<=i.fi && i.se<=y)
		{
			num[a[i.fi]][1]--;
			num[a[i.se]][1]--;
			res++;
		}
	}*/
	res+=num[1][1]+num[2][1]+num[3][1]-max(num[1][1],max(num[2][1],num[3][1]));
	return res;
}

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