Submission #1009623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009623		oyber	Mutating DNA (IOI21_dna)	C++17	100 / 100	33 ms	9672 KiB

dna

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

vector<int> a;
vector<int> b;
int n;

vector<vector<int>> prefix;

int char_to_num(char c) {
	if (c == 'A') {
		return 0;
	}
	if (c == 'C') {
		return 1;
	}
	return 2;
}

void init(string A, string B) {
	n = A.size();

	for (int i = 0; i < n; i++) {
		a.push_back(char_to_num(A[i]));
		b.push_back(char_to_num(B[i]));
	}

	prefix.resize(9, {0});
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 9; j++) {
			prefix[j].push_back(prefix[j][i]);
		}
		int x = a[i]*3+b[i];
		prefix[x][i+1] = prefix[x][i]+1;
	}
}

int get_distance(int x, int y) {
	vector<int> num(9);
	for (int i = 0; i < 9; i++) {
		num[i] = prefix[i][y+1] - prefix[i][x];
	}

	if (!(num[0]+num[3]+num[6] == num[0]+num[1]+num[2] && num[1]+num[4]+num[7] == num[3]+num[4]+num[5])) {
		return -1;
	}

	int swaps = 0;

	int ac = min(num[1], num[3]);
	swaps += ac;
	num[1] -= ac;
	num[3] -= ac;

	int at = min(num[2], num[6]);
	swaps += at;
	num[2] -= at;
	num[6] -= at;

	int ct = min(num[5], num[7]);
	swaps += ct;
	num[5] -= ct;
	num[7] -= ct;

	int s = num[1]+num[3]+num[2]+num[6]+num[5]+num[7];
	swaps += (s/3)*2;

	return swaps;
}

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