Submission #524912

#	Time	Username	Problem	Language	Result	Execution time	Memory
524912		Leonardo_Paes	Mutating DNA (IOI21_dna)	C++17	100 / 100	60 ms	9148 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef pair<int,int> pii;
#define f first
#define s second

string s, t;
int n, k, qtd[maxn][10], aux[maxn][3];

void init(string a, string b){
	s = ' ' + a, t = ' ' + b;
	n = (int)s.size();
	k = 9;
	for(int i=1; i<n; i++){
		if(t[i] == 'A') --aux[i][0];
		if(t[i] == 'C') --aux[i][1];
		if(t[i] == 'T') --aux[i][2];
		if(s[i] == 'A'){
			++aux[i][0];
			if(t[i] == 'A') ++qtd[i][0];
			else if(t[i] == 'C') ++qtd[i][1];
			else ++qtd[i][2];
		}
		else if(s[i] == 'C'){
			++aux[i][1];
			if(t[i] == 'A') ++qtd[i][3];
			else if(t[i] == 'C') ++qtd[i][4];
			else ++qtd[i][5];
		}
		else{
			++aux[i][2];
			if(t[i] == 'A') ++qtd[i][6];
			else if(t[i] == 'C') ++qtd[i][7];
			else ++qtd[i][8];
		}
		for(int j=0; j<k; j++) qtd[i][j] += qtd[i-1][j];
		for(int j=0; j<3; j++) aux[i][j] += aux[i-1][j];
	}
}

int get_distance(int x, int y){
	++x, ++y;
	for(int i=0; i<3; i++) if(aux[y][i] - aux[x-1][i] != 0) return -1;
	int ans = 0;
	int wtf = 0;
	vector<pii> kras = {{1, 3}, {2, 6}, {5, 7}};
	for(pii a : kras){
		int u = a.f, v = a.s;
		int mx = max(qtd[y][u] - qtd[x-1][u], qtd[y][v] - qtd[x-1][v]);
		int mn = min(qtd[y][u] - qtd[x-1][u], qtd[y][v] - qtd[x-1][v]);
		ans += mn;
		wtf += mx - mn;
	}
	return ans + (wtf/3*2);
}

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