Submission #437252

#	Time	Username	Problem	Language	Result	Execution time	Memory
437252		errorgorn	Mutating DNA (IOI21_dna)	C++17	100 / 100	54 ms	6536 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

int n;

int cnta_s[100005];
int cntt_s[100005];

int cnta_t[100005];
int cntt_t[100005];

int cntat[100005];
int cntta[100005];

int cntac[100005];
int cntca[100005];

int cnttc[100005];
int cntct[100005];

void init(std::string s, std::string t) {
	n=sz(s);
	
	rep(x,0,n) cnta_s[x+1]=cnta_s[x]+(s[x]=='A');
	rep(x,0,n) cntt_s[x+1]=cntt_s[x]+(s[x]=='T');
	
	rep(x,0,n) cnta_t[x+1]=cnta_t[x]+(t[x]=='A');
	rep(x,0,n) cntt_t[x+1]=cntt_t[x]+(t[x]=='T');
	
	rep(x,0,n) cntat[x+1]=cntat[x]+(s[x]=='A' && t[x]=='T');
	rep(x,0,n) cntta[x+1]=cntta[x]+(s[x]=='T' && t[x]=='A');
	rep(x,0,n) cntac[x+1]=cntac[x]+(s[x]=='A' && t[x]=='C');
	rep(x,0,n) cntca[x+1]=cntca[x]+(s[x]=='C' && t[x]=='A');
	rep(x,0,n) cnttc[x+1]=cnttc[x]+(s[x]=='T' && t[x]=='C');
	rep(x,0,n) cntct[x+1]=cntct[x]+(s[x]=='C' && t[x]=='T');
}

int get_distance(int l, int r) {
	if (cnta_s[r+1]-cnta_s[l]!=cnta_t[r+1]-cnta_t[l]) return -1;	
	if (cntt_s[r+1]-cntt_s[l]!=cntt_t[r+1]-cntt_t[l]) return -1;
	
	int at=cntat[r+1]-cntat[l];
	int ta=cntta[r+1]-cntta[l];
	int ac=cntac[r+1]-cntac[l];
	int ca=cntca[r+1]-cntca[l];
	int tc=cnttc[r+1]-cnttc[l];
	int ct=cntct[r+1]-cntct[l];
	
	//cout<<at<<" "<<ta<<" "<<ac<<" "<<ca<<" "<<tc<<" "<<ct<<endl;
	
	int ans=0;
	int temp;
	
	temp=min(at,ta);
	ans+=temp;
	at-=temp,ta-=temp;
	
	temp=min(ac,ca);
	ans+=temp;
	ac-=temp,ca-=temp;
	
	temp=min(tc,ct);
	ans+=temp;
	tc-=temp,ct-=temp;
	
	ans+=2*(at+ta);
	
	return ans;
}

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