Submission #1128537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128537		Gabriel	Mutating DNA (IOI21_dna)	C++17	100 / 100	119 ms	15236 KiB

dna

#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
long long n;
unordered_map<string, long long> Cambiar;
unordered_map<long long, string> iCambiar;
vector< vector<long long> > Pares, Letrasa, Letrasb;
void init(string a, string b){
	n = a.size();
	Pares.assign(9, vector<long long>(n, 0));
	Letrasa.assign(3, vector<long long>(n, 0));
	Letrasb.assign(3, vector<long long>(n, 0));
	for(long long i = 0; i < 3; i++){
		for(long long j = 0; j < 3; j++){
			string c = "  ";
			if(i == 0) c[0] = 'A';
			if(i == 1) c[0] = 'C';
			if(i == 2) c[0] = 'T';
			if(j == 0) c[1] = 'A';
			if(j == 1) c[1] = 'C';
			if(j == 2) c[1] = 'T';
			Cambiar[c] = i * 3 + j;
			iCambiar[i * 3 + j] = c;
		}
		string c = " ";
		if(i == 0) c[0] = 'A';
		if(i == 1) c[0] = 'C';
		if(i == 2) c[0] = 'T';
		Cambiar[c] = i;
		iCambiar[i] = c;
	}
	for(long long i = 0; i < n; i++){
		string c = "", cc = "", ccc = "";
		c += a[i];
		c += b[i];
		cc += a[i];
		ccc += b[i];
		Pares[Cambiar[c]][i]++;
		Letrasa[Cambiar[cc]][i]++;
		Letrasb[Cambiar[ccc]][i]++;
		if(i > 0){
			for(long long j = 0; j < 9; j++) Pares[j][i] += Pares[j][i - 1];
			for(long long j = 0; j < 3; j++) Letrasa[j][i] += Letrasa[j][i - 1];
			for(long long j = 0; j < 3; j++) Letrasb[j][i] += Letrasb[j][i - 1];
		}
	}
}
int get_distance(int x, int y){
	x--;
	vector<long long> c(9);
	for(long long i = 0; i < 9; i++) c[i] = Pares[i][y];
	for(long long i = 0; i < 9 and x > -1; i++) c[i] -= Pares[i][x];
	for(long long i = 0; i < 3; i++){
		long long ka = Letrasa[i][y], kb = Letrasb[i][y];
		if(x > -1){
			ka -= Letrasa[i][x];
			kb -= Letrasb[i][x];
		}
		if(ka != kb) return -1;
	}
	int r = 0, m, Extra = 0;
	m = min(c[Cambiar["AC"]], c[Cambiar["CA"]]);
	r += m;
	c[Cambiar["AC"]] -= m;
	c[Cambiar["CA"]] -= m;
	Extra += c[Cambiar["AC"]];
	Extra += c[Cambiar["CA"]];
	m = min(c[Cambiar["AT"]], c[Cambiar["TA"]]);
	r += m;
	c[Cambiar["AT"]] -= m;
	c[Cambiar["TA"]] -= m;
	Extra += c[Cambiar["AT"]];
	Extra += c[Cambiar["TA"]];
	m = min(c[Cambiar["TC"]], c[Cambiar["CT"]]);
	r += m;
	c[Cambiar["TC"]] -= m;
	c[Cambiar["CT"]] -= m;
	Extra += c[Cambiar["TC"]];
	Extra += c[Cambiar["CT"]];
	r += Extra * 2 / 3;
	return r;
}

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