Submission #783506

#	Time	Username	Problem	Language	Result	Execution time	Memory
783506		Sir_Ahmed_Imran	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	34 ms	9740 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define ll int
int pre[100010][3][3];
int cnt[100010][3];
int cnt1[100010][3];
void init(string a,string b)
{
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			pre[0][i][j]=0;
		}
	}
	cnt[0][0]=0; cnt[0][1]=0; cnt[0][2]=0; cnt1[0][0]=0; cnt1[0][1]=0; cnt1[0][2]=0;
	for(int i=0;i<(int)a.size();i++)
	{
		if(a[i]=='T')
		{
			a[i]='B';
		}
		if(b[i]=='T')
		{
			b[i]='B';
		}
		for(int l=0;l<3;l++)
		{
			for(int j=0;j<3;j++)
			{
				pre[i+1][l][j]=pre[i][l][j];
			}
		}
		cnt[i+1][0]=cnt[i][0];
		cnt[i+1][1]=cnt[i][1];
		cnt[i+1][2]=cnt[i][2];
		cnt1[i+1][0]=cnt1[i][0];
		cnt1[i+1][1]=cnt1[i][1];
		cnt1[i+1][2]=cnt1[i][2];
		pre[i+1][a[i]-'A'][b[i]-'A']++;
		cnt[i+1][a[i]-'A']++;
		cnt1[i+1][b[i]-'A']++;
	}
}
int get_distance(int x,int y)
{
	int aa1=cnt[y+1][0]-cnt[x][0];
	int ab1=cnt[y+1][1]-cnt[x][1];
	int ac1=cnt[y+1][2]-cnt[x][2];
	int ba1=cnt1[y+1][0]-cnt1[x][0];
	int bb1=cnt1[y+1][1]-cnt1[x][1];
	int bc1=cnt1[y+1][2]-cnt1[x][2];
	if(aa1!=ba1 or ab1!=bb1 or ac1!=bc1)
	{
		return -1;
	}
	ll ab=pre[y+1][0][1]-pre[x][0][1];
	ll ac=pre[y+1][0][2]-pre[x][0][2];
	ll ba=pre[y+1][1][0]-pre[x][1][0];
	ll bc=pre[y+1][1][2]-pre[x][1][2];
	ll ca=pre[y+1][2][0]-pre[x][2][0];
	ll cb=pre[y+1][2][1]-pre[x][2][1];
	ll ans=0,ex=min(ab,ba);
	ans+=ex;
	ab-=ex;
	ba-=ex;
	ex=min(ac,ca);
	ans+=ex;
	ac-=ex;
	ca-=ex;
	ex=min(bc,cb);
	ans+=ex;
	bc-=ex;
	cb-=ex;
	ex=min(ab,min(bc,ca));
	ans+=(ex*2);
	ab-=ex;
	bc-=ex;
	ca-=ex;
	ex=min(ba,min(cb,ac));
	ans+=(ex*2);
	ba-=ex;
	cb-=ex;
	ac-=ex;
	return ans;
}

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