Submission #702998

#	Time	Username	Problem	Language	Result	Execution time	Memory
702998		n1k	Mutating DNA (IOI21_dna)	C++17	71 / 100	1556 ms	3788 KiB

dna

#include <bits/stdc++.h>

#define ll long long
#define vt vector
#define pb push_back
#define ar array
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()

using namespace std;

/*
 1. simplify
 2. add new elements
 3. brute force solution
 4. optimize
 5. start implementing
*/

// --- templates ---

// --- code ---

string a, b;

void init(string aa, string bb){
	a = aa;
	b = bb;
}

int get_distance(int x, int y){
	map<char, int> m = {
		{'A', 0},
		{'T', 1},
		{'C', 2}
	};

	vt<vt<int>> adj(3, vt<int>(3));
	vt<int> c(3);
	for(int i = x; i <= y; i++){
		if(a[i] != b[i])
			adj[m[a[i]]][m[b[i]]]++;

		c[m[a[i]]]++;
		c[m[b[i]]]--;
	}
	if(c[0] || c[1] || c[2]){
		return -1;
	}

	int ans = 0;
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			if(adj[i][j] && adj[j][i]){
				int take = min(adj[i][j], adj[j][i]);
				ans += take;
				adj[i][j] -= take;
				adj[j][i] -= take;
			}else{
				for(int k = 0; k < 3; k++){
					int take = min({adj[i][j], adj[j][k], adj[k][i]});
					adj[i][j] -= take, adj[j][k] -= take, adj[k][i] -= take;
					ans += 2 * take;
				}
			}
		}
	}

	return ans;
}

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