Submission #491713

#	Time	Username	Problem	Language	Result	Execution time	Memory
491713		maksim1744	Mutating DNA (IOI21_dna)	C++17	100 / 100	52 ms	7404 KiB

dna

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

int n;
array<array<vector<int>, 3>, 3> v;

void init(std::string a, std::string b) {
	n = a.size();
	for (int i = 0; i < n; ++i) {
	    if (a[i] == 'T') a[i] = 'B';
	    if (b[i] == 'T') b[i] = 'B';
	}
	for (int i = 0; i < 3; ++i) {
	    for (int j = 0; j < 3; ++j) {
	        v[i][j].assign(n + 1, 0);
	    }
	}
	for (int i = 0; i < n; ++i) {
		for (int a = 0; a < 3; ++a) {
		    for (int b = 0; b < 3; ++b) {
		        v[a][b][i + 1] = v[a][b][i];
		    }
		}
		v[a[i] - 'A'][b[i] - 'A'][i + 1]++;
	}
}

int get_distance(int x, int y) {
	int ans = 0;
	array<array<int, 3>, 3> c;
	array<int, 3> tot = {0, 0, 0};
	for (int i = 0; i < 3; ++i) {
	    for (int j = 0; j < 3; ++j) {
	    	if (i == j) continue;
	        c[i][j] = v[i][j][y + 1] - v[i][j][x];
	        tot[i] += c[i][j];
	        tot[j] -= c[i][j];
	    }
	}
	if (count(tot.begin(), tot.end(), 0) != 3) return -1;
	int left = 0;
	for (int i = 0; i < 3; ++i) {
	    for (int j = 0; j < i; ++j) {
	    	int cur = min(c[i][j], c[j][i]);
	    	c[i][j] -= cur;
	    	c[j][i] -= cur;
	    	left = c[i][j] + c[j][i];
	    	ans += cur;
	    }
	}
	ans += left * 2;
	return ans;
}

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