Submission #873135

#	Time	Username	Problem	Language	Result	Execution time	Memory
873135		Muhammad_Aneeq	Mutating DNA (IOI21_dna)	C++17	56 / 100	27 ms	6932 KiB

dna

#include "dna.h"
#include <map>
#include <iostream>
using namespace std;
int const N=1e5+10;
int pre[2][3][N]={};
int n;
int dif[N]={};
map<char,int>d;
void init(string a,string b) 
{
	d['A']=0;d['C']=1;d['T']=2;
	n=a.size();
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<3;j++)
			pre[0][j][i+1]=pre[0][j][i];
		pre[0][d[a[i]]][i+1]++;
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<3;j++)
			pre[1][j][i+1]=pre[1][j][i];
		pre[1][d[b[i]]][i+1]++;
	}
	for (int i=0;i<n;i++)
		dif[i+1]=dif[i]+(a[i]!=b[i]);
}	
int get_distance(int x, int y)
{
	y++;
	for (int i=0;i<3;i++)
	{
		if (pre[0][i][y]-pre[0][i][x]!=pre[1][i][y]-pre[1][i][x])
		{
			return -1;
		}
	}
	return (dif[y]-dif[x]+1)/2;
}

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