Submission #634554

#	Time	Username	Problem	Language	Result	Execution time	Memory
634554		Alan	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	7372 KiB

dna

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

int cnt[100005][3][3], c[256];

int ps (int x, int y, int i, int j) {
	return cnt[y][i][j] - (x ? cnt[x-1][i][j] : 0);
}

void init(string a, string b) {
	c['A'] = 0;
	c['T'] = 1;
	c['C'] = 2;
	int n = a.size();
	for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++) if (j != k)
		cnt[i][j][k] = (c[(int) a[i]] == j && c[(int) b[i]] == k) + (i ? cnt[i-1][j][k] : 0);
}

int get_distance(int x, int y) {
	int diff[3][3], ans = 0;
	for (int i = 0; i < 2; i++) for (int j = i+1; j < 3; j++) {
		diff[i][j] = abs(ps(x, y, i, j) - ps(x, y, j, i));
		ans += min(ps(x, y, i, j), ps(x, y, j, i));
	}
	if (diff[0][1] == diff[0][2] && diff[0][2] == diff[1][2])
		if ((ps(x, y, 0, 1) > ps(x, y, 1, 0)) == (ps(x, y, 1, 2) > ps(x, y, 2, 1)) && (ps(x, y, 1, 2) > ps(x, y, 2, 1)) == (ps(x, y, 2, 0) > ps(x, y, 0, 2)))
			return ans + (diff[0][1] + diff[0][2] + diff[1][2]) * 2 / 3;
	return -1;
}

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