Submission #1067987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067987		ezdp	Mutating DNA (IOI21_dna)	C++17	35 / 100	86 ms	23560 KiB

dna

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

template<class T> using matrix = vector<vector<T>>;

int n;
vector<matrix<int>> pref;

void init(string a, string b){
	n = a.size();
	for(int i = 0; i < n; i ++){
		int A = (a[i] == 'A' ? 0 : (a[i] == 'T' ? 1 : 2));
		int B = (b[i] == 'A' ? 0 : (b[i] == 'T' ? 1 : 2));
		if(pref.empty()) pref.push_back(matrix<int>(3, vector<int>(3)));
		else pref.push_back(pref.back());
		++ pref.back()[A][B];
	}
}

int get_distance(int x, int y){
	matrix<int> left = (x ? pref[x - 1] : matrix<int>(3, vector<int>(3, 0)));
	matrix<int> right = pref[y];
	matrix<int> diff(3, vector<int>(3, 0));
	for(int i = 0; i < 3; i ++){
		for(int j = 0; j < 3; j ++){
			diff[i][j] = right[i][j] - left[i][j];
		}
	}
	int ans = 0;
	for(int i = 0; i < 3; i ++) for(int j = i + 1; j < 3; j ++){
		int t = min(diff[i][j], diff[j][i]);
		ans += t;
		diff[i][j] -= t;
		diff[j][i] -= t;
	}
	// 0 > 1 > 2
	{
		int t = min({diff[0][1], diff[1][2], diff[2][0]});
		ans += t;
		diff[0][1] -= t;
		diff[1][2] -= t;
		diff[2][0] -= t;
	}
	// 0 > 2 > 1
	{
		int t = min({diff[0][2], diff[2][1], diff[1][0]});
		ans += t;
		diff[0][2] -= t;
		diff[2][1] -= t;
		diff[1][0] -= t;
	}
	int excess = 0;
	for(int i = 0; i < 3; i ++){
		for(int j = 0; j < 3; j ++){
			if(i == j) continue;
			excess += diff[i][j];
		}
	}
	return (excess ? -1 : ans);
}

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