Submission #580570

#	Time	Username	Problem	Language	Result	Execution time	Memory
580570		MODDI	Mutating DNA (IOI21_dna)	C++17	100 / 100	248 ms	13500 KiB

dna

//#include "grader.cpp"
//#include "dna.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
string str1, str2;
int n;
int tree[6][400000];
int get(char a, char b){
	if(a == 'A' && b == 'C')
		return 0;
	else if(a == 'A' && b == 'T')
		return 1;
	else if(a == 'C' && b == 'T')
		return 2;
	else if(a == 'C' && b == 'A')
		return 3;
	else if(a == 'T' && b == 'A')
		return 4;
	else 
		return 5;
}
void build(int node, int l, int r){
	if(l == r){
		if(str1[l] != str2[l])
			tree[get(str1[l], str2[l])][node] = 1;
	}
	else{
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		tree[0][node] = tree[0][node * 2] + tree[0][node * 2 + 1];
		tree[1][node] = tree[1][node * 2] + tree[1][node * 2 + 1];
		tree[2][node] = tree[2][node * 2] + tree[2][node * 2 + 1];
		tree[3][node] = tree[3][node * 2] + tree[3][node * 2 + 1];
		tree[4][node] = tree[4][node * 2] + tree[4][node * 2 + 1];
		tree[5][node] = tree[5][node * 2] + tree[5][node * 2 + 1];
	}
}
int query(int node, int l, int r, int L, int R, int id){
	if(r < L || l > R)
		return 0;
	if(L <= l && r <= R)
		return tree[id][node];
		
	int mid = (l + r) / 2;
	int left = query(node * 2, l, mid, L, R, id);
	int right = query(node * 2 + 1, mid + 1, r, L, R, id);
	return left + right;
}
void init(string a, string b){
	n = a.size();
	str1 = a;
	str2 = b;
	memset(tree, 0, sizeof(tree));
	build(1, 0, n-1);
}
int get_distance(int x, int y) {
	int l = x, r = y;
	int calc[6];
	bool zero = true;
	for(int i = 0; i < 6; i++){
		calc[i] = query(1, 0, n-1, l, r, i);
		if(calc[i] != 0)
			zero = false;
		//cout<<calc[i]<<" ";
		//cout<<calc[i]<<endl;
	}
	//cout<<endl;
	if(zero)
		return 0;
	int ans = 0;
	int sm = min(calc[0], calc[3]);
	ans += sm;
	calc[0] -= sm;
	calc[3] -= sm;
	sm = min(calc[1], calc[4]);
	ans += sm;
	calc[1] -= sm;
	calc[4] -= sm;
	sm = min(calc[2],calc[5]);
	ans += sm;
	calc[2] -= sm;
	calc[5] -= sm;
	bool pos = true;
	if(calc[0] == 0 && calc[2] == 0 && calc[4] == 0){
		if(calc[1] == calc[3] && calc[3] == calc[5]){
			ans += calc[1] * 2;
		}
		else
			pos = false;
	} 
	else if(calc[1] == 0 && calc[3] == 0 && calc[5] == 0){
		if(calc[0] == calc[2] && calc[2] == calc[4]){
			ans += calc[0] * 2;
		}
		else
			pos = false;
	}
	else
		pos = false;
		
	if(!pos)
		return -1;
	else
		return ans;
}

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