Submission #915957

#	Time	Username	Problem	Language	Result	Execution time	Memory
915957		ByeWorld	Mutating DNA (IOI21_dna)	C++17	71 / 100	1529 ms	3900 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 num[4][4], n;

void init(string a, string b) {
	s = a; t = b;
	// for(int i=1; i<=n; i++){
	// 	for(int j=1; j<=3; j++){
	// 		pa[i][j] = pa[i-1][j]; pb[i][j] = pb[i-1][j];
	// 	}
	// 	if(a[i]=='A') pa[i][1]++;
	// 	else if(a[i]=='C') pa[i][2]++;
	// 	else pa[i][3]++;
	// 	if(b[i]=='A')pb[i][1]++;
	// 	else if(b[i]=='C') pb[i][2]++;
	// 	else pb[i][3]++;
	// }
}
int at,ta,tc,ct,ac,ca;
int get_distance(int x, int y) {
	at=0,ta=0,tc=0,ct=0,ac=0,ca=0;
	for(int i=x; i<=y; i++){
		if(s[i]==t[i]) continue;
		if(s[i]=='A'){
			if(t[i]=='C') ac++;
			else at++;
		} else if(s[i]=='C'){
			if(t[i]=='A') ca++;
			else ct++;
		} else {
			if(t[i]=='A') ta++;
			else tc++;
		}
	}
	//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: 0 / 13
• Subtask 4: 28 / 28
• Subtask 5: 0 / 16