Submission #1079737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079737		GusterGoose27	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	8724 KiB

dna

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

using namespace std;

const int MAXN = 1e5+5;
int pre[MAXN][3][3];
int num[MAXN][3];
int n;

int nsum(int l, int r, int v) {
	return num[r+1][v] - num[l][v];
}

int psum(int l, int r, int v1, int v2) {
	return pre[r+1][v1][v2] - pre[l][v1][v2];
}

void init(string a, string b) {
	n = a.size();
	map<char, int> conv({{'A', 0}, {'C', 1}, {'T', 2}});
	for (int i = 0; i < n; i++) {
		int u = conv[a[i]];
		int v = conv[b[i]];
		pre[i+1][u][v] = 1;
		num[i+1][u]++;
		num[i+1][v]--;
		for (int a = 0; a < 3; a++) {
			for (int b = 0; b < 3; b++) pre[i+1][a][b] += pre[i][a][b];
			num[i+1][a] += num[i][a];
		}
	}
}

int get_distance(int x, int y) {
	for (int i = 0; i < 3; i++) if (nsum(x, y, i) != 0) return -1;
	int s = 0;
	for (int i = 0; i < 3; i++) {
		int j = (i+1)%3;
		int u = psum(x, y, i, j), v = psum(x, y, j, i);
		s += min(u, v);
		if (i == 0) s += 2*(max(u, v) - min(u, v));
	}
	return s;
}

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