Submission #703000

#	Time	Username	Problem	Language	Result	Execution time	Memory
703000		n1k	DNA 돌연변이 (IOI21_dna)	C++17	71 / 100	1591 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++){
			int take = min(adj[i][j], adj[j][i]);
			ans += take;
			adj[i][j] -= take;
			adj[j][i] -= take;
		}
	}

	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			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