Submission #623860

#	Time	Username	Problem	Language	Result	Execution time	Memory
623860		hfoliacots	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	13008 KiB

dna

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

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

//v[i][0] = ac, v[i][1] = at, v[i][2] = ca, v[i][3] = ct, v[i][4] = ta, v[i][5] = tc
vvi p;

void init(string a, string b) {
	int n = a.size();
	vvi v(n, vi(6, 0));
	for (int i = 0; i < n; i++) {
		if(a[i] == 'A' and b[i] == 'C') v[i][0]++;
		else if(a[i] == 'A' and b[i] == 'T') v[i][1]++;
		else if(a[i] == 'C' and b[i] == 'A') v[i][2]++;
		else if(a[i] == 'C' and b[i] == 'T') v[i][3]++;
		else if(a[i] == 'T' and b[i] == 'A') v[i][4]++;
		else if(a[i] == 'T' and b[i] == 'C') v[i][5]++;
	}
	p = vvi(n+1, vi(6, 0));
	for (int i = 1; i < n+1; i++) {
		p[i][0] = p[i-1][0]+v[i-1][0];
		p[i][1] = p[i-1][1]+v[i-1][1];
		p[i][2] = p[i-1][2]+v[i-1][2];
		p[i][3] = p[i-1][3]+v[i-1][3];
		p[i][4] = p[i-1][4]+v[i-1][4];
		p[i][5] = p[i-1][5]+v[i-1][5];
	}
}

int get_distance(int x, int y) {
	y++;
	int ac = p[y][0] - p[x][0], at = p[y][1] - p[x][1], ca = p[y][2] - p[x][2];
	int ct = p[y][3] - p[x][3], ta = p[y][4] - p[x][4], tc = p[y][5] - p[x][5];
	
	//cout << ac << ' ' << at << ' ' << ca << ' ' << ct << ' ' << ta << ' ' << tc << endl;
	
	int a = min(ac, ca), b = min(at, ta), c = min(ct, tc);
	int r = a+b+c;
	ac -= a;
	at -= b;
	ca -= a;
	ct -= c;
	ta -= b;
	tc -= c;
	
	if (ac == ct && ac == ta) {
		r += ac+ct;
		ac = 0;
		ta = 0;
		ct = 0;
	}
	if (at == ca && at == tc) {
		r += at+ca;
		at = 0;
		ca = 0;
		tc = 0;
	}
	
	//cout << ac << ' ' << at << ' ' << ca << ' ' << ct << ' ' << ta << ' ' << tc << endl;
	
	if (ac > 0 || at > 0 || ca > 0 || ct > 0 || ta > 0 || tc > 0) return -1;
	return r;
}

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