Submission #780149

#	Time	Username	Problem	Language	Result	Execution time	Memory
780149		Lyrically	Mutating DNA (IOI21_dna)	C++17	0 / 100	28 ms	6832 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int pre[100005][6];
int acta[100005][3],actb[100005][3];
int n;
char trans(char p)
{
	return p=='A'?'a':(p=='C'?'b':'c');
}
void init(string a,string b)
{
	a=" "+a;b=" "+b;
	n=(int)a.size()-1;
	rep1(i,n)
	{
		a[i]=trans(a[i]);
		b[i]=trans(b[i]);
	}
	rep1(i,n)
	{
		rep(j,6){pre[i][j]=pre[i-1][j];}
		rep(j,3){acta[i][j]=acta[i-1][j];}
		acta[i][a[i]-'a']++;
		rep(j,3){actb[i][j]=actb[i-1][j];}
		actb[i][b[i]-'a']++;
		if(a[i]==b[i]){continue;}
		if(a[i]=='a'&&b[i]=='b'){pre[i][0]++;}
		if(a[i]=='a'&&b[i]=='c'){pre[i][1]++;}
		if(a[i]=='b'&&b[i]=='a'){pre[i][2]++;}
		if(a[i]=='b'&&b[i]=='c'){pre[i][3]++;}
		if(a[i]=='c'&&b[i]=='a'){pre[i][4]++;}
		if(a[i]=='c'&&b[i]=='b'){pre[i][5]++;}
	}
}
int get_distance(int x,int y)
{
	x++,y++;
	rep(i,3)
	{
		if(acta[y][i]-acta[x-1][i]!=actb[y][i]-actb[x-1][i])
		{
			return -1;
		}
	}
	int npre[6];
	rep(i,6)
	{
		npre[i]=pre[y][i]-pre[x-1][i];
	}
	int rans=min(npre[0],npre[2])+min(npre[1],npre[4])+min(npre[3],npre[5]);
	npre[0]-=min(npre[0],npre[2]);
	npre[2]-=min(npre[0],npre[2]);
	npre[1]-=min(npre[1],npre[4]);
	npre[4]-=min(npre[1],npre[4]);
	npre[3]-=min(npre[3],npre[5]);
	npre[5]-=min(npre[3],npre[5]);
	if(npre[0]||npre[1]||npre[2]||npre[3]||npre[4]||npre[5])
	{
		int mx=0;
		rep(i,6){mx=max(mx,npre[i]);}
		return rans+mx*2;
	}
	return rans;
}

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