Submission #1149291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149291		ReLice	Mutating DNA (IOI21_dna)	C++20	100 / 100	48 ms	9576 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define ll int
#define vll vector<ll>
#define pb push_back
#define bc back()
using namespace std;
const ll N=2e5+7;
ll pref[3][3][N];
ll sum[3][N];
ll sum2[3][N];
vll s,s2;
void init(std::string a, std::string b) {
	map<char,ll> mp;
	mp['A']=0;
	mp['C']=1;
	mp['T']=2;
	for(int i=0;i<(ll)a.size();i++){
		s.pb(mp[a[i]]);
		s2.pb(mp[b[i]]);
		sum[s.bc][i]++;
		sum2[s2.bc][i]++;
		if(s.bc!=s2.bc)pref[s.bc][s2.bc][i]++;
		if(i==0)continue;
		for(int j=0;j<3;j++){
			for(int q=0;q<3;q++){
				pref[j][q][i]+=pref[j][q][i-1];
			}
		}
		for(int j=0;j<3;j++)sum[j][i]+=sum[j][i-1];
		for(int j=0;j<3;j++)sum2[j][i]+=sum2[j][i-1];
	}
}

int get_distance(int x, int y) {
	ll i,j,q;
	for(i=0;i<3;i++){
		if(x==0){
			if(sum[i][y]!=sum2[i][y])return -1;
			continue;
		}
		if(sum[i][y]-sum[i][x-1]!=sum2[i][y]-sum2[i][x-1])return -1;
	}
	ll ans=0;
	ll v[3][3];
	memset(v,0,sizeof(v));
	// edges
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(i==j)continue;
			ll a;
			if(x) a=pref[i][j][x-1];
			else a=0;
			v[i][j]=pref[i][j][y];
			v[i][j]-=a;
			ans+=v[i][j];
		}
	}
	// two cycles
	for(i=0;i<3;i++){
		for(j=i+1;j<3;j++){
			ll mn=min(v[i][j],v[j][i]);
			ans-=mn;
			v[i][j]-=mn;
			v[j][i]-=mn;
		}
	}
	
	//three cycles
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(i==j)continue;
			for(q=0;q<3;q++){
				if(i==q || j==q)continue;
				ll mn=min(v[i][j],min(v[j][q],v[q][i]));
				ans-=mn;
				v[i][j]-=mn;
				v[j][q]-=mn;
				v[q][i]-=mn;
			}
		}
	}
	return ans;
}

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