Submission #873151

#	Time	Username	Problem	Language	Result	Execution time	Memory
873151		Muhammad_Aneeq	Mutating DNA (IOI21_dna)	C++17	0 / 100	37 ms	8976 KiB

dna

#include "dna.h"
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int const N=1e5+10;
int pre[2][3][N]={};
int n;
int dif[3][3][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++)
	{
		for (int j=0;j<3;j++)
			for (int k=0;k<3;k++)
				dif[j][k][i+1]=dif[j][k][i];
		dif[d[a[i]]][d[b[i]]][i+1]++;
	}
}
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;
		}
	}
	int pr[3][3]={};
	for (int i=0;i<3;i++)
		for (int j=0;j<3;j++)
			pr[i][j]=dif[i][j][y]-dif[i][j][x];
	int ans=0;
	vector<int>z;
	z.push_back(pr[1][2]);z.push_back(pr[0][1]);z.push_back(pr[2][0]);
	sort(z.begin(), z.end());
	ans+=2*z[0];
	z={pr[0][2],pr[2][1],pr[1][0]};
	sort(z.begin(), z.end());
	ans+=2*z[0];
	return ans;
}

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