Submission #1199373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199373		TimDee	Mutating DNA (IOI21_dna)	C++20	100 / 100	29 ms	6152 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()

const int N=1e5+5;

int A[N], C[N], T[N];
int AA[N], AT[N], AC[N];
int CA[N], CT[N], CC[N];
int TA[N], TT[N], TC[N];

void init(string a, string b) {
	int n=a.size();
	forn(i,n) {
		A[i+1]=A[i]+(a[i]=='A')-(b[i]=='A');
		C[i+1]=C[i]+(a[i]=='C')-(b[i]=='C');
		T[i+1]=T[i]+(a[i]=='T')-(b[i]=='T');
		AT[i+1]=AT[i] + ( (a[i]=='A') && (b[i]=='T') );
		AC[i+1]=AC[i] + ( (a[i]=='A') && (b[i]=='C') );
		CT[i+1]=CT[i] + ( (a[i]=='C') && (b[i]=='T') );
		TC[i+1]=TC[i] + ( (a[i]=='T') && (b[i]=='C') );
		CA[i+1]=CA[i] + ( (a[i]=='C') && (b[i]=='A') );
		TA[i+1]=TA[i] + ( (a[i]=='T') && (b[i]=='A') );
	}
}
int get_distance(int x, int y) {
	int a = A[y+1]-A[x];
	if (a) return -1;
	int c = C[y+1]-C[x];
	if (c) return -1;
	int t = T[y+1]-T[x];
	if (t) return -1;

	int at=AT[y+1]-AT[x];
	int ct=CT[y+1]-CT[x];
	int ac=AC[y+1]-AC[x];
	int tc=TC[y+1]-TC[x];
	int ca=CA[y+1]-CA[x];
	int ta=TA[y+1]-TA[x];

	int ans=0;
	int z;
	z = min(at,ta);
	ans+=z;
	at-=z;
	ta-=z;

	z = min(ac,ca);
	ans+=z;
	ac-=z;
	ca-=z;

	z = min(ct,tc);
	ans+=z;
	ct-=z;
	tc-=z;

	ans+=2*(ac+ca);

	return ans;
}

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