Submission #780117

#	Time	Username	Problem	Language	Result	Execution time	Memory
780117		Lyrically	Mutating DNA (IOI21_dna)	C++17	56 / 100	31 ms	8516 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 act=npre[0]+npre[2]-2*min(npre[0],npre[2]);
	int p=npre[1]+npre[4]-2*min(npre[1],npre[4]);
	int q=npre[3]+npre[5]-2*min(npre[3],npre[5]);
	if(act==0||p==0||q==0)
	{
		return max({npre[0],npre[1],npre[3]});
	}
	return act*2;
}

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