Submission #598868

#	Time	Username	Problem	Language	Result	Execution time	Memory
598868		idiot123	Mutating DNA (IOI21_dna)	C++17	100 / 100	121 ms	13104 KiB

dna

#include<bits/stdc++.h>
#include "dna.h"

using namespace std;

int minSwaps(array<array<int, 3>, 3> a){
	int res = 0;
	int x = min(a[0][1], a[1][0]);
	res += x;
	a[0][1] -= x;
	a[1][0] -= x;
	x = min(a[0][2], a[2][0]);
	res += x;
	a[0][2] -= x;
	a[2][0] -= x;
	x = min(a[1][2], a[2][1]);
	res += x;
	a[1][2] -= x;
	a[2][1] -= x;
	if(a[0][1] + a[0][2] != a[1][0] + a[2][0] || a[1][0] + a[1][2] != a[0][1] + a[0][2] || a[2][0] + a[2][1] != a[0][2] + a[1][2])return -1;
	res += 2 * (a[0][1] + a[0][2] + a[1][0] + a[1][2] + a[2][0] + a[2][1])/3;
	return res;
}

class Tree{
	private:
	int lrSize = 2;
	vector<array<array<int, 3>, 3>> v;
	
	void update(int pos){
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				v[pos][i][j] = v[2*pos][i][j] + v[2*pos + 1][i][j];
			}
		}
	}
	
	void rangeSum(int a, int b, int l, int r, int pos, array<array<int,3>, 3>& ans){
		if(b < l || r < a)return;
		if(a <= l && r <= b){
			for(int i = 0; i < 3; i++){
				for(int j = 0; j < 3; j++)ans[i][j] += v[pos][i][j];
			}
		}else{
			int m = (l + r)/2;
			rangeSum(a, b, l, m, 2*pos, ans);
			rangeSum(a, b, m+1, r, 2*pos+1, ans);
		}
	}
	
	public:
	void init(string a, string b){
		int n = a.length();
		while(lrSize < n)lrSize *= 2;
		v.resize(2*lrSize);
		for(int i = 0; i < lrSize; i++){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 3; k++){
					v[lrSize + i][j][k] = 0;
				}
			}
			int x, y;
			if(a[i] == 'A') x = 0;
			else if(a[i] == 'T')x=1;
			else x = 2;
			if(b[i] == 'A') y = 0;
			else if(b[i] == 'T')y=1;
			else y = 2;
			if(i < n){
				v[lrSize+i][x][y] = 1;
			}
		}
		for(int i = lrSize - 1; i >= 1; i--)update(i);
	}
	
	Tree(){
		
	}
	
	int getAns(int a, int b){
		array<array<int, 3>, 3> ans;
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++)ans[i][j] = 0;
		}
		rangeSum(a, b, 0, lrSize-1, 1, ans);
		return minSwaps(ans);
	}
};

Tree tree;

void init(string a, string b){
	tree.init(a, b);
}

int get_distance(int x, int y){
	return tree.getAns(x, y);
}
/*
int main(){
	int n, q; cin>>n>>q;
	string a, b; cin>>a>>b;
	init(a, b);
	for(int i = 0; i < q; i++){
		int x, y; cin>>x>>y;
		cout<<get_distance(x, y)<<"\n";
	}
}*/

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