Submission #703003

#	Time	Username	Problem	Language	Result	Execution time	Memory
703003		n1k	Mutating DNA (IOI21_dna)	C++17	100 / 100	69 ms	8780 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;

map<char, int> m = {
	{'A', 0},
	{'T', 1},
	{'C', 2}
};

const int N = 100000 + 5;


int pc[N][3], padj[N][3][3];
 
void init(string aa, string bb){
	memset(pc, 0, sizeof pc);
	memset(padj, 0, sizeof padj);

	a = aa;
	b = bb;
	int n = sz(a);

	for(int i = 0; i < n; i++){
		if(i){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 3; k++){
					padj[i][j][k] = padj[i - 1][j][k];
				}
				pc[i][j] = pc[i - 1][j];
			}
		}

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

	for(int i = 0; i < 3; i++){
		c[i] = pc[y][i] - (x ? pc[x - 1][i] : 0);
	}

	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			adj[i][j] = padj[y][i][j] - (x ? padj[x - 1][i][j] : 0);
		}
	}

	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: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16