Submission #898403

#	Time	Username	Problem	Language	Result	Execution time	Memory
898403		aqxa	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	9760 KiB

dna

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

const int N = 1e5 + 10; 
int pa[N][3], pb[N][3], n, p[N][3][3], c[3][3]; 

void init(string a, string b) {
	n = a.size(); 
	for (int i = 0; i < n; ++i) {
		int ca = (a[i] == 'A' ? 0 : (a[i] == 'T' ? 1 : 2)); 
		int cb = (b[i] == 'A' ? 0 : (b[i] == 'T' ? 1 : 2)); 
		
		pa[i + 1][ca]++; 
		pb[i + 1][cb]++; 
		p[i + 1][ca][cb]++; 
		for (int j = 0; j < 3; ++j) {
			pa[i + 1][j] += pa[i][j]; 
			pb[i + 1][j] += pb[i][j]; 
			for (int k = 0; k < 3; ++k) {
				p[i + 1][j][k] += p[i][j][k]; 
			}
		}
	}
}

int get_distance(int x, int y) {
	for (int i = 0; i < 3; ++i) {
		if (pa[y + 1][i] - pa[x][i] != pb[y + 1][i] - pb[x][i]) {
			return -1; 
		}
	}
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			c[i][j] = p[y + 1][i][j] - p[x][i][j]; 
		}
	}
	int ans = 0; 
	for (int i = 0; i < 3; ++i) {
		for (int j = i + 1; j < 3; ++j) {
			int z = min(c[i][j], c[j][i]); 
			c[i][j] -= z; 
			c[j][i] -= z; 
			ans += z; 
		}
	}
	vector<int> d0, d1; 
	for (int i = 0; i < 3; ++i) {
		d0.push_back(c[i][(i + 1) % 3]);
		d1.push_back(c[i][(i + 2) % 3]); 
	}
	sort(d0.begin(), d0.end()); 
	sort(d1.begin(), d1.end()); 
	assert(d0[0] == d0[2] && d1[0] == d1[2]); 
	assert(d0[0] == 0 || d1[0] == 0); 
	return 2 * (d0[0] + d1[0]) + ans; 
}
 
// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
	
// 	int m, q; 
// 	cin >> m >> q; 
// 	string a, b; 
// 	for (int i = 0; i < m; ++i) {
// 		int c = rand() % 3; 
// 		if (c == 0) a += 'A'; 
// 		if (c == 1) a += 'T'; 
// 		if (c == 2) a += 'C'; 
// 	}
// 	b = a; 
// 	random_shuffle(b.begin(), b.end()); 
// 	init(a, b); 
// 	cout << a << "\n";
// 	cout << b << "\n";

// 	for (int i = 0; i < m; ++i) {
// 		for (int j = i; j < m; ++j) {
// 			cout << "! " << i << ' ' << j << ' ' << get_distance(i, j) << '\n';
// 		}
// 	}
 
// 	return 0; 
// }	 

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