Submission #1271220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271220		asdasdqwer	Mutating DNA (IOI21_dna)	C++17	100 / 100	24 ms	6148 KiB

dna

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

#include "dna.h"

#define tii array<array<int,3>, 3>

tii operator+(const tii &x, const tii &y) {
	tii res;
	for (int i=0;i<3;i++) 
		for (int j=0;j<3;j++) 
			res[i][j] = x[i][j] + y[i][j];
	
	return res;
}

tii operator-(const tii &x, const tii &y) {
	tii res;
	for (int i=0;i<3;i++) 
		for (int j=0;j<3;j++) 
			res[i][j] = x[i][j] - y[i][j];
	
	return res;
}


void print(tii arr) {
	for (int i=0;i<3;i++) {
		for (int j=0;j<3;j++) 
			cout << arr[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}

int conv(char c) {
	if (c == 'A') return 0;
	else if (c == 'T') return 1;
	return 2;
}

vector<tii> p;

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

int get_distance(int x, int y) {
	tii arr = p[y];
	if (x) {
		arr = arr - p[x-1];
	}

	int result = 0;
	for (int i=0;i<3;i++) arr[i][i] = 0;

	for (int i=0;i<3;i++) {
		for (int j=0;j<3;j++) {
			int mn = min(arr[i][j], arr[j][i]);
			result += mn;
			arr[i][j] -= mn;
			arr[j][i] -= mn;
		}
	}

	for (int i=0;i<3;i++) {
		for (int j=0;j<3;j++) {
			if (arr[i][j] == 0) continue;
			int other = 3 - i - j;
			int mn = min(arr[i][j], min(arr[j][other], arr[other][i]));

			arr[i][j] -= mn;
			arr[j][other] -= mn;
			arr[other][i] -= mn;
			result += 2*mn;
		}
	}

	for (int i=0;i<3;i++) {
		for (int j=0;j<3;j++) {
			if (arr[i][j]) return -1;
		}
	}
	
	return result;
}

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