Submission #1195741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195741		Ludissey	Mutating DNA (IOI21_dna)	C++20	100 / 100	58 ms	33864 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;
vector<vector<int>> cA,cB;
vector<vector<vector<int>>> tA;
vector<int> A,B;


void init(std::string a, std::string b) {
	cA.clear();
	cB.clear();
	tA.clear();
	A.clear();
	B.clear();
	cA.resize(sz(a)+1,vector<int>(3,0));
	cB.resize(sz(a)+1,vector<int>(3,0));
	tA.resize(sz(a)+1,vector<vector<int>>(3,vector<int>(3,0)));
	A.resize(sz(a)+1,0);
	B.resize(sz(a)+1,0);
	for (int i = 1; i <= sz(a); i++)
	{
		char c=a[i-1];
		if(c=='A') A[i]=0;
		else if(c=='T') A[i]=1;
		else if(c=='C') A[i]=2;
		cA[i][A[i]]++;

		c=b[i-1];
		if(c=='A') B[i]=0;
		else if(c=='T') B[i]=1;
		else if(c=='C') B[i]=2;
		cB[i][B[i]]++;
		if(i>0){
			for (int j = 0; j < 3; j++)
			{
				cA[i][j]+=cA[i-1][j];
				cB[i][j]+=cB[i-1][j];
			}
		}
		tA[i][A[i]][B[i]]++;
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				tA[i][j][k]+=tA[i-1][j][k];
			}
		}
	}
	
}

int get_distance(int x, int y) {
	x++;
	y++;
	for (int j = 0; j < 3; j++)
	{
		if(cA[y][j]-cA[x-1][j]!=cB[y][j]-cB[x-1][j]) return -1;
	}
	int sm=0;
	for (int j = 0; j < 3; j++)
	{
		for (int k = 0; k < 3; k++)
		{
			if(j==k) continue;
			sm+=tA[y][j][k]-tA[x-1][j][k];
		}
	}
	int rem=0;
	for (int j = 0; j < 3; j++)
	{
		for (int k = j+1; k < 3; k++)
		{
			rem+=min(tA[y][j][k]-tA[x-1][j][k],tA[y][k][j]-tA[x-1][k][j]);
		}
	}
	return max(0,(sm-rem*2)-(sm-rem*2)/3)+rem;
}

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