Submission #986419

#	Time	Username	Problem	Language	Result	Execution time	Memory
986419		Pyqe	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	10688 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

const long long ma=3;
const string ky="ATC";
long long n,ps[ma][ma][100069],fq[ma][ma];

inline long long yk(char ch)
{
	long long i;
	
	for(i=0;i<ma;i++)
	{
		if(ky[i]==ch)
		{
			return i;
		}
	}
	return -1;
}

void init(string s,string s2)
{
	long long i,j,r,k,l;
	
	n=s.length();
	for(i=1;i<=n;i++)
	{
		k=yk(s[i-1]);
		l=yk(s2[i-1]);
		for(j=0;j<ma;j++)
		{
			for(r=0;r<ma;r++)
			{
				ps[j][r][i]=ps[j][r][i-1];
			}
		}
		ps[k][l][i]++;
	}
}

int get_distance(int lb,int rb)
{
	long long i,j,k,l,w,sm,z=0;
	
	lb++;
	rb++;
	for(i=0;i<ma;i++)
	{
		for(j=0;j<ma;j++)
		{
			fq[i][j]=ps[i][j][rb]-ps[i][j][lb-1];
		}
	}
	for(i=0;i<ma;i++)
	{
		sm=0;
		for(j=0;j<ma;j++)
		{
			sm+=fq[i][j]-fq[j][i];
		}
		if(sm)
		{
			return -1;
		}
	}
	for(i=0;i<ma;i++)
	{
		l=(i+1)%ma;
		w=min(fq[i][l],fq[l][i]);
		z+=w;
		fq[i][l]-=w;
		fq[l][i]-=w;
		k=max(fq[i][l],fq[l][i]);
	}
	z+=k*2;
	return z;
}

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