Submission #437525

#	Time	Username	Problem	Language	Result	Execution time	Memory
437525		Sho10	Mutating DNA (IOI21_dna)	C++17	100 / 100	78 ms	8616 KiB

dna

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#define ll int
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
string a,b;
ll n,cnt[7][1000005],viz[3][4][1000005];
void init(string A,string B){
a=A;
b=B;
n=a.size();
a=" "+a;
b=" "+b;
for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=3;j++)
    {
        viz[1][j][i]=viz[1][j][i-1];
        viz[2][j][i]=viz[2][j][i-1];
    }
if(a[i]=='A'){
    viz[1][1][i]++;
}else if(a[i]=='C'){
viz[1][2][i]++;
}else if(a[i]=='T'){
viz[1][3][i]++;
}
if(b[i]=='A'){
    viz[2][1][i]++;
}else if(b[i]=='C'){
viz[2][2][i]++;
}else if(b[i]=='T'){
viz[2][3][i]++;
}
for(ll j=1;j<=6;j++)
{
cnt[j][i]=cnt[j][i-1];
}
if(a[i]=='A'&&b[i]=='C'){
    cnt[1][i]++;
}else if(a[i]=='A'&&b[i]=='T'){
cnt[2][i]++;
}else if(a[i]=='C'&&b[i]=='T'){
cnt[3][i]++;
}else if(a[i]=='C'&&b[i]=='A'){
cnt[4][i]++;
}else if(a[i]=='T'&&b[i]=='A'){
cnt[5][i]++;
}else if(a[i]=='T'&&b[i]=='C'){
cnt[6][i]++;
}
}
return;
}
int get_distance(int x,int y){
x++;
y++;
for(ll j=1;j<=3;j++)
{
    if(viz[1][j][y]-viz[1][j][x-1]!=viz[2][j][y]-viz[2][j][x-1]){
        return -1;
    }
}
ll ans=0;
ll mn=INF;
ll s[7];
for(ll j=1;j<=6;j++)
{
    s[j]=cnt[j][y]-cnt[j][x-1];
}
mn=min(s[1],s[4]);
ans+=mn;
s[1]-=mn;
s[4]-=mn;
mn=min(s[2],s[5]);
ans+=mn;
s[2]-=mn;
s[5]-=mn;
mn=min(s[3],s[6]);
ans+=mn;
s[3]-=mn;
s[6]-=mn;
ans+=(s[1]+s[2]+s[3]+s[4]+s[5]+s[6])/3*2;
return ans;
}

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