Submission #488134

#	Time	Username	Problem	Language	Result	Execution time	Memory
488134		8e7	Mutating DNA (IOI21_dna)	C++17	100 / 100	60 ms	6800 KiB

dna

//Challenge: Accepted
#include "dna.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		ind++;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		ind++;
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} b[9];
int s[maxn], t[maxn];
void init(string a, string bb){
	int n = a.size();
	for (int i = 0;i < n;i++) {
		s[i] = (a[i] == 'A' ? 0 : (a[i] == 'T' ? 1 : 2));
		t[i] = (bb[i] == 'A' ? 0 : (bb[i] == 'T' ? 1 : 2));
		b[s[i]*3 + t[i]].modify(i, 1);
	}
}
int get_distance(int l, int r) {
	int type[9];
	for (int i = 0;i < 9;i++) {
		type[i] = b[i].query(r) - b[i].query(l-1);
	}	
	if (type[1] + type[2] != type[3] + type[6] || type[3] + type[5] != type[1] + type[7]) {
		return -1;
	}
	type[0] = type[4] = type[8] = 0;	
	int p[3][2] = {{1, 3}, {2, 6}, {5, 7}};	
	int ans = 0, rem = 0;
	for (int i = 0;i < 3;i++) {
		int val = min(type[p[i][0]], type[p[i][1]]);
		type[p[i][0]] -= val;
		type[p[i][1]] -= val;
		ans += val;
		rem = max(type[p[i][0]], type[p[i][1]]);
	}
	return ans + rem * 2;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/

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