Submission #850229

#	Time	Username	Problem	Language	Result	Execution time	Memory
850229		StefanSebez	Mutating DNA (IOI21_dna)	C++17	0 / 100	1597 ms	1060188 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];
vector<pair<int,int> >par;
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=0;i<n;i++)
	{
		for(int j=1;j<n;j++)
		{
			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(auto i:par)
	{
		if(x<=i.fi && i.se<=y)
		{
			num[a[i.fi]][1]--;
			num[a[i.se]][1]--;
			num[b[i.fi]][2]--;
			num[b[i.se]][2]--;
			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: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16