Submission #1268800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268800		FaresSTH	Mutating DNA (IOI21_dna)	C++20	100 / 100	25 ms	6472 KiB

dna

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
const char ch[]={'A','C','T'};
int id(char c){
	if(c=='A')return 0;
	if(c=='T')return 1;
	return 2;
}
int nd[1000001][3][3],n;
string a,b;
void init(string A, string B){
	n=A.size();
	a='#'+A,b='#'+B;
	for(int i=1;i<=n;i++){
		nd[i][id('A')][id('T')]=nd[i-1][id('A')][id('T')];
		nd[i][id('A')][id('C')]=nd[i-1][id('A')][id('C')];
		nd[i][id('T')][id('A')]=nd[i-1][id('T')][id('A')];
		nd[i][id('T')][id('C')]=nd[i-1][id('T')][id('C')];
		nd[i][id('C')][id('A')]=nd[i-1][id('C')][id('A')];
		nd[i][id('C')][id('T')]=nd[i-1][id('C')][id('T')];
		nd[i][id('A')][id('A')]=nd[i-1][id('A')][id('A')];
		nd[i][id('C')][id('C')]=nd[i-1][id('C')][id('C')];
		nd[i][id('T')][id('T')]=nd[i-1][id('T')][id('T')];
		nd[i][id(a[i])][id(b[i])]++;
	}
}
int get_distance(int l, int r){
	l++; r++; // convert 0-based query to 1-based prefix
	int f[3][3]={},frq[3]={};
	for(char i:ch){
		for(char j:ch){
			f[id(i)][id(j)]=nd[r][id(i)][id(j)]-nd[l-1][id(i)][id(j)];
			frq[id(i)]+=f[id(i)][id(j)];
			frq[id(j)]-=f[id(i)][id(j)];
		}
	}
	for(char i:ch)if(frq[id(i)])return -1;
	int res=0;
	for(char i:ch){
		for(char j:ch){
			if(j<=i)continue;
			int m=min(f[id(i)][id(j)],f[id(j)][id(i)]);
			f[id(i)][id(j)]-=m;
			f[id(j)][id(i)]-=m;
			res+=m;
		}
	}
	int s=0;
	for(char i:ch)for(char j:ch)if(i!=j)s+=f[id(i)][id(j)];
	return res+2*(s/3);
}
// MalekLoky 3mk

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