Submission #591386

#	Time	Username	Problem	Language	Result	Execution time	Memory
591386		SuhaibSawalha1	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	7420 KiB

dna

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

const int N = 1e5 + 1;
int n, P[N][3][3];

int get (char c) {
	switch(c) {
		case 'A': return 0;
		case 'C': return 1;
		default: return 2;
	}
}

void init(string a, string b) {
	n = a.size();
	for (int i = 1; i <= n; ++i) {
		++P[i][get(a[i - 1])][get(b[i - 1])];
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				P[i][j][k] += P[i - 1][j][k];
			}
		}
	}
}

int get_distance(int x, int y) {
	++y;
	int ans = 0;
	int a[3][3];
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			a[i][j] = P[y][i][j] - P[x][i][j];
			// cout << i << " " << j << " " << a[i][j] << endl;
		}
	}
	// cout << "GOOOD" << endl;;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			if (i == j) {
				continue;
			}
			int k = 3 - i - j;
			int t = min(a[i][j], a[j][i]);
			a[i][j] -= t;
			a[j][i] -= t;
			ans += t;
			t = min(a[i][j], a[k][i]);
			a[i][j] -= t;
			a[k][i] -= t;
			a[k][j] += t;
			ans += t;
			if (a[i][j]) {
				return -1;
			}
		}
	}
	return ans;
}

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