Submission #1048286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048286		parsadox2	Mutating DNA (IOI21_dna)	C++17	100 / 100	24 ms	10076 KiB

dna

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

using namespace std;

const int N = 1e5 + 10;
int n , psum[N][3][3] , suma[N][3] , sumb[N][3];
string a , b;

int f(char c)
{
	if(c == 'A')
		return 0;
	else if(c == 'C')
		return 1;
	else
		return 2;
}

void init(string aa, string bb) {
	n = aa.size();
	a = aa;
	b = bb;
	suma[0][f(a[0])] = 1;
	sumb[0][f(b[0])] = 1;
	psum[0][f(a[0])][f(b[0])] = 1;
	for(int i = 1 ; i < n ; i++)
	{
		for(int j = 0 ; j < 3 ; j++)
		{
			suma[i][j] = suma[i - 1][j];
			sumb[i][j] = sumb[i - 1][j];
			for(int k = 0 ; k < 3 ; k++)
				psum[i][j][k] = psum[i - 1][j][k];
		}
		suma[i][f(a[i])]++;
		sumb[i][f(b[i])]++;
		psum[i][f(a[i])][f(b[i])]++;
	}
}

int get_distance(int x, int y) {
	int cnt[3][3];
	int ca[3] , cb[3];
	for(int i = 0 ; i < 3 ; i++)
	{
		ca[i] = suma[y][i];
		cb[i] = sumb[y][i];
		for(int j = 0 ; j < 3 ; j++)
			cnt[i][j] = psum[y][i][j];
	}
	if(x > 0)
	{
		for(int i = 0 ; i < 3 ; i++)
		{
			ca[i] -= suma[x - 1][i];
			cb[i] -= sumb[x - 1][i];
			for(int j = 0 ; j < 3 ; j++)
				cnt[i][j] -= psum[x - 1][i][j];
		}
	}
	for(int i = 0 ; i < 3 ; i++)  if(ca[i] != cb[i])
		return -1;
	int ans = 0;
	for(int i = 0 ; i < 2 ; i++)  for(int j = i + 1 ; j < 3 ; j++)
	{
		int mn = min(cnt[i][j] , cnt[j][i]);
		cnt[i][j] -= mn;
		cnt[j][i] -= mn;
		ans += mn;
	}
	for(int i = 0 ; i < 2 ; i++)
	{
		ans += cnt[i][2];
		ans += cnt[2][i];
	}
	return ans;
}

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