Submission #774727

#	Time	Username	Problem	Language	Result	Execution time	Memory
774727		SanguineChameleon	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	8584 KiB

dna

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

const int maxn = 1e5 + 20;
int diff[maxn][3];
int cnt[maxn][3][3];

void init(string a, string b) {
	int n = a.size();
	for (int i = 1; i <= n; i++) {
		for (int x = 0; x < 3; x++) {
			diff[i][x] = diff[i - 1][x];
			for (int y = 0; y < 3; y++) {
				cnt[i][x][y] = cnt[i - 1][x][y];
			}
		}
		int x = a[i - 1] == 'A' ? 0 : a[i - 1] == 'T' ? 1 : 2;
		int y = b[i - 1] == 'A' ? 0 : b[i - 1] == 'T' ? 1 : 2;
		cnt[i][x][y]++;
		diff[i][x]++;
		diff[i][y]--;
	}
}

int get_distance(int lt, int rt) {
	lt++;
	rt++;
	for (int x = 0; x < 3; x++) {
		if (diff[rt][x] != diff[lt - 1][x]) {
			return -1;
		}
	}
	int res = 0;
	for (int x = 0; x < 3; x++) {
		for (int y = x + 1; y < 3; y++) {
			res += min(cnt[rt][x][y] - cnt[lt - 1][x][y], cnt[rt][y][x] - cnt[lt - 1][y][x]);
		}
	}
	res += abs((cnt[rt][0][1] - cnt[lt - 1][0][1]) - (cnt[rt][1][0] - cnt[lt - 1][1][0])) * 2;
	return res;
}

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