Submission #1274731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274731		vlomaczk	Mutating DNA (IOI21_dna)	C++20	100 / 100	95 ms	33936 KiB

dna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n;
int M = 100'010;
vector<int> A(M), B(M);
vector<vector<vector<int>>> prefix(M, vector<vector<int>>(3, vector<int>(3, 0)));
vector<vector<int>> prefA(M, vector<int>(3, 0)), prefB(M, vector<int>(3, 0));

int change(char c) {
	if(c=='A') return 0;
	if(c=='T') return 1;
	return 2;
}

void init(string a, string b) {
	n = a.size();
	for(int i=0; i<n; ++i) A[i+1] = change(a[i]);
	for(int i=0; i<n; ++i) B[i+1] = change(b[i]);
	for(int i=1; i<=n; ++i) {
		for(int x=0; x<3; ++x) for(int y=0; y<3; ++y) prefix[i][x][y] = prefix[i-1][x][y];
		prefix[i][A[i]][B[i]]++;
		for(int x=0; x<3; ++x) for(int y=0; y<3; ++y) prefA[i][x] += prefix[i][x][y];
		for(int x=0; x<3; ++x) for(int y=0; y<3; ++y) prefB[i][x] += prefix[i][y][x];
	}
}

int get_distance(int l, int r) {
	++l; ++r;
	vector<vector<int>> t(3, vector<int>(3, 0));
	for(int x=0; x<3; ++x) for(int y=0; y<3; ++y) t[x][y] = prefix[r][x][y] - prefix[l-1][x][y]; 
	for(int x=0; x<3; ++x) if(prefA[r][x]-prefA[l-1][x] != prefB[r][x] - prefB[l-1][x]) return -1;
	int ans = 0;
	ans += min(t[0][1], t[1][0]) + min(t[1][2], t[2][1]) + min(t[0][2], t[2][0]);
	ans += 2*abs(t[0][1]-t[1][0]);
	return ans;
}

/*int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, q;
	cin >> n >> q;
	
	string a,b;
	cin >> a >> b;

	init(a,b);
	while(q--) {
		int l,r; 
		cin >> l >> r;
		cout << get_distance(l,r) << "\n";
	}

	return 0;
}*/

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