Submission #1061647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061647		amine_aroua	Mutating DNA (IOI21_dna)	C++17	100 / 100	135 ms	43196 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;

int code(char c)
{
	if(c == 'A')
		return 0;
	if(c == 'C')
		return 1;
	return 2;
}
vector<vector<vector<int>>> pref;
vector<vector<vector<int>>> occ;
void init(std::string a, std::string b) {
	int n = (int)a.size();
	pref.assign(n + 1 , vector<vector<int>>(3 , vector<int>(3 , 0)));
	occ = pref;
	a = '.' + a;
	b = '.' + b;
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 0 ; j < 3 ; j++)
		{
			occ[i][0][j] = occ[i - 1][0][j];
			occ[i][1][j] = occ[i - 1][1][j];
			for(int k = 0 ;k < 3 ; k++)
			{
				pref[i][j][k]+=pref[i - 1][j][k];
			}
		}
		occ[i][0][code(a[i])]++;
		occ[i][1][code(b[i])]++;
		pref[i][code(a[i])][code(b[i])]++;
	}
}

int get_distance(int x, int y) {
	x++ , y++;
	for(int i = 0 ; i < 3 ; i++)
	{
		if(occ[y][0][i] - occ[x - 1][0][i] != occ[y][1][i] - occ[x - 1][1][i])
		{
			return -1;
		}
	}
	vector<int> r;
	int ans = 0;
	for(int i = 0 ; i < 3 ; i++)
	{
		for(int j = i + 1 ; j < 3 ; j++)
		{
			int a = pref[y][i][j] - pref[x - 1][i][j] , b = pref[y][j][i] - pref[x - 1][j][i];
			if(a  > b)
				swap(a , b);
			ans+=a;
			b-=a;
			r.push_back(b);
		}
	}
	for(int i = 0  ;i< min((int)r.size() , 2) ; i++)
	{
		ans+=r[i];
	}
	return ans;
}

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