Submission #744675

#	Time	Username	Problem	Language	Result	Execution time	Memory
744675		Ocean_MO	Mutating DNA (IOI21_dna)	C++17	0 / 100	51 ms	14148 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define inf LLONG_MAX
#define pll pair<ll,ll>
#define pb push_back

// O n*q
ll asum[3][100005]={},bsum[3][100005]={},indeg[3][3][100005]={};
ll n;
string aa,bb;
int turn(char c){
	if(c=='A')return 0;
	if(c=='C')return 1;
	return 2;
}
void init(std::string a, std::string b) {
	n=a.size();
	aa=a;
	bb=b;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<3;j++)asum[j][i+1]=asum[j][i];
		for(ll j=0;j<3;j++)bsum[j][i+1]=bsum[j][i];
		asum[turn(a[i])][i+1]++;
		bsum[turn(b[i])][i+1]++;
	}
	for(ll i=0;i<n;i++){
		for(ll j=0;j<3;j++){
			for(ll k=0;k<3;k++)indeg[j][k][i+1]=indeg[j][k][i];
		}
		if(b[i]!=a[i]){
			indeg[turn(b[i])][turn(a[i])][i+1]++;
		}
	}
}

ll l;
int get_distance(int x, int y) {
	for(ll i=0;i<3;i++){
		ll temp=asum[i][y+1]-asum[i][x],temp2=bsum[i][y+1]-bsum[i][x];
		if(temp!=temp2)return -1;
	}
	ll ans=0;
	ll buff[3][3]={};
	for(ll i=0;i<3;i++){
		for(ll j=0;j<3;j++){
			buff[i][j]=indeg[i][j][y+1]-indeg[i][j][x];
		}
	}
	for(ll i=0;i<3;i++){
		for(ll j=0;j<3;j++){
			if(i==j)continue;
			ll temp=min(buff[i][j],buff[j][i]);
			ans+=temp;
			buff[i][j]-=temp;
			buff[j][i]-=temp;
		}
	}
	bool v=0;
	if(buff[0][1]==buff[1][2]&&buff[1][2]==buff[2][0]){
		v=1;ans+=2*buff[0][1];
    }
	if(buff[1][0]==buff[2][1]&&buff[0][2]==buff[2][1]){
		v=1;ans+=2*buff[2][1];
	}
	if(v==1)return -1;
	return ans;
}

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