Submission #791510

#	Time	Username	Problem	Language	Result	Execution time	Memory
791510		acatmeowmeow	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	9716 KiB

dna

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

using namespace std;

//#define int long long 

const int N = 1e5;
int n, prefix1[3][N + 5], prefix2[3][N + 5], prefix[N + 5][3][3];

void init(std::string a, std::string b) {
	n = a.size();
	a = '#' + a, b = '#' + b;
	for (int i= 1; i <= n; i++) {
		int ch = a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2);
		prefix1[ch][i] = 1;
		for (int j = 0; j < 3; j++) prefix1[j][i] += prefix1[j][i - 1];
	}
	for (int i = 1; i <= n; i++) {
		int ch = b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2);
		prefix2[ch][i] = 1;
		for (int j = 0; j < 3; j++) prefix2[j][i] += prefix2[j][i - 1];
	}
	for (int i = 1; i <= n; i++) {
		int ch1 = a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2);
		int ch2 = b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2);
		prefix[i][ch1][ch2] = 1;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				prefix[i][j][k] += prefix[i - 1][j][k];
			}
		}
	}
}

int cnt[3][3];

int get_distance(int x, int y) {
	x++, y++;
	for (int i = 0; i < 3; i++) if(prefix1[i][y] - prefix1[i][x - 1] != prefix2[i][y] - prefix2[i][x - 1]) return -1;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cnt[i][j] = prefix[y][i][j] - prefix[x - 1][i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = i + 1; j < 3; j++) {
			int d = min(cnt[i][j], cnt[j][i]);
			ans += d;
			cnt[i][j] -= d, cnt[j][i] -= d;
		}
	}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) continue;
			int k = 3 - i - j, d = min({cnt[i][j], cnt[j][k], cnt[k][i]});
			ans += 2*d;
			cnt[i][j] -= d, cnt[j][k] -= d, cnt[k][i] -= d;
		}
	}
	return ans;
}


/*signed main() {
	int n, q;
	//assert(scanf("%d %d", &n, &q) == 2);
	cin >> n >> q;
	char A[n+1], B[n+1];
	//assert(scanf("%s", A) == 1);
	//assert(scanf("%s", B) == 1);
	cin >> A >> B;
	std::string a = std::string(A);
	std::string b = std::string(B);
	std::vector<int> x(q), y(q);
	for (int i = 0; i < q; i++) {
		//assert(scanf("%d %d", &x[i], &y[i]) == 2);
		cin >> x[i] >> y[i];
	}
	//fclose(stdin);
	std::vector<int> results(q);
	init(a, b);
	for (int i = 0; i < q; i++) {
		results[i] = get_distance(x[i], y[i]);
	}
	for (int i = 0; i < q; i++) {
		printf("%d\n", results[i]);
	}
	//fclose(stdout);
	return 0;
}*/

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