Submission #915981

#	Time	Username	Problem	Language	Result	Execution time	Memory
915981		ByeWorld	Mutating DNA (IOI21_dna)	C++17	100 / 100	40 ms	6620 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define bupol __builtin_popcount
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+10;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+9;
const int SQRT = 520;
const int INF = 1e9+10;
typedef pair<ll,ll> pii;
typedef pair<int, pii> ipii;

string s, t; int n;
int AT[MAXN], TA[MAXN], AC[MAXN], CA[MAXN], TC[MAXN], CT[MAXN];

void init(string a, string b) {
	s = '.'+a; t = '.'+b; n = a.size(); 
	for(int i=1; i<=n; i++){
		AT[i]=AT[i-1];
		TA[i]=TA[i-1];
		CT[i]=CT[i-1];
		TC[i]=TC[i-1];
		AC[i]=AC[i-1];
		CA[i]=CA[i-1];

		if(s[i]=='A'){
			if(t[i]=='C') AC[i]++;
			else if(t[i]=='T') AT[i]++;
		} else if(s[i]=='C'){
			if(t[i]=='A') CA[i]++;
			else if(t[i]=='T') CT[i]++;
		} else {
			if(t[i]=='A') TA[i]++;
			else if(t[i]=='C') TC[i]++;
		}
	}
}
int at,ta,tc,ct,ac,ca;
int get_distance(int x, int y) {
	x++; y++;
	at=AT[y]-AT[x-1],ta=TA[y]-TA[x-1],tc=TC[y]-TC[x-1],ct=CT[y]-CT[x-1],
	ac=AC[y]-AC[x-1],ca=CA[y]-CA[x-1];

	//cout << CA[y] << ' ' << CA[x-1] << ' ' << " p\n";

	//cout<<ca<<' '<<ac<<' '<<at<<' '<<ta<<' '<< ct<<' '<< tc << " p\n";
	int ans = 0;
	int te = min(ac,ca); ans += te;
	ac -= te; ca -= te;
	te = min(at, ta); ans += te;
	at -= te; ta -= te;
	te = min(ct, tc); ans += te;
	ct -= te; tc -= te;

	te = min(min(ca, at), tc); ans += 2*te;
	ca -= te; at -= te; tc -= te;
	te = min(min(ac, ct), ta); ans += 2*te;
	ac -= te; ct -= te; ta -= te;
	
	if(ac!=0||ca!=0||at!=0||ta!=0||ct!=0||tc!=0) return -1;
	return ans;
}

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