Submission #443658

#	Time	Username	Problem	Language	Result	Execution time	Memory
443658		Xellos	Mutating DNA (IOI21_dna)	C++17	100 / 100	71 ms	6060 KiB

dna

#include "dna.h"
#include <vector>
using namespace std;

static string C = "ATC";
static vector<int> cnt[3][3];

void init(string a, string b) {
	int N = a.length();
	for(int k = 0; k < 9; k++) cnt[k/3][k%3].resize(N+1, 0);
	for(int j = 0; j < 3; j++)
		for(int k = 0; k < 3; k++)
			for(int i = 0; i < N; i++)
				cnt[j][k][i+1] = (a[i] == C[j] && b[i] == C[k]);
	for(int j = 0; j < 3; j++)
		for(int k = 0; k < 3; k++)
			for(int i = 0; i < N; i++)
				cnt[j][k][i+1] += cnt[j][k][i];
}

int get_distance(int x, int y) {
	int cnt_sub[3][3];
	for(int j = 0; j < 3; j++)
		for(int k = 0; k < 3; k++)
			cnt_sub[j][k] = cnt[j][k][y+1] - cnt[j][k][x];
	for(int i = 0; i < 3; i++) {
		int d = 0;
		for(int j = 0; j < 3; j++) d += cnt_sub[i][j];
		for(int j = 0; j < 3; j++) d -= cnt_sub[j][i];
		if(d) return -1;
	}
	cnt_sub[0][0] = cnt_sub[1][1] = cnt_sub[2][2] = 0;
	int ret = 0;
	for(int i = 0; i < 9; i++) {
		int m = min(cnt_sub[i/3][i%3], cnt_sub[i%3][i/3]);
		ret += m;
		cnt_sub[i/3][i%3] -= m;
		cnt_sub[i%3][i/3] -= m;
	}
	int s = 0;
	for(int i = 0; i < 9; i++) s += cnt_sub[i/3][i%3];
	ret += s/3*2;
	return ret;
}

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