Submission #1236858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236858		colossal_pepe	Mutating DNA (IOI21_dna)	C++17	35 / 100	78 ms	33096 KiB

dna

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

int n;
vector<vector<int>> cnt_a, cnt_b;
vector<vector<vector<int>>> mut;

int id(char c) {
	if (c == 'A') return 0;
	else if (c == 'T') return 1;
	else return 2;
}

void init(string a, string b) {
	n = a.size();
	cnt_a.resize(n + 1, vector<int>(3, 0)), cnt_b.resize(n + 1, vector<int>(3, 0));
	mut.resize(n + 1, vector<vector<int>>(3, vector<int>(3, 0)));
	for (int i = 1; i <= n; i++) {
		cnt_a[i][id(a[i - 1])]++, cnt_b[i][id(b[i - 1])]++;
		mut[i][id(a[i - 1])][id(b[i - 1])]++;
		for (int j = 0; j < 3; j++) {
			cnt_a[i][j] += cnt_a[i - 1][j];
			cnt_b[i][j] += cnt_b[i - 1][j];
			for (int k = 0; k < 3; k++) {
				mut[i][j][k] += mut[i - 1][j][k];
			}
		}
	}
}

int get_distance(int x, int y) {
	vector<vector<int>> mut_cur(3, vector<int>(3, 0));
	for (int i = 0; i < 3; i++) {
		if (cnt_a[y + 1][i] - cnt_a[x][i] != cnt_b[y + 1][i] - cnt_b[x][i]) return -1;
		for (int j = 0; j < 3; j++) {
			mut_cur[i][j] = mut[y + 1][i][j] - mut[x][i][j];
		}
	}
	return mut_cur[0][1] + mut_cur[0][2] + mut_cur[1][2];
}

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