Submission #542840

#	Time	Username	Problem	Language	Result	Execution time	Memory
542840		alexdumitru	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	8956 KiB

dna

#include <bits/stdc++.h>
using namespace std;
int sa1[100005],st1[100005],sc1[100005],sa2[100005],st2[100005],sc2[100005];
int pepoz[100005];
int AT[100005];
int AC[100005];
int CA[100005];
int CT[100005];
int TA[100005];
int TC[100005];
int geta1(int i, int j)
{
    if(!i)return sa1[j];
    return sa1[j]-sa1[i-1];
}
int gett1(int i, int j)
{
    if(!i)return st1[j];
    return st1[j]-st1[i-1];
}
int getc1(int i, int j)
{
    if(!i)return sc1[j];
    return sc1[j]-sc1[i-1];
}
int geta2(int i, int j)
{
    if(!i)return sa2[j];
    return sa2[j]-sa2[i-1];
}

int getat(int i, int j)
{
    if(!i)return AT[j];
    return AT[j]-AT[i-1];
}
int getac(int i, int j)
{
    if(!i)return AC[j];
    return AC[j]-AC[i-1];
}
int getca(int i, int j)
{
    if(!i)return CA[j];
    return CA[j]-CA[i-1];
}
int getct(int i, int j)
{
    if(!i)return CT[j];
    return CT[j]-CT[i-1];
}
int getta(int i, int j)
{
    if(!i)return TA[j];
    return TA[j]-TA[i-1];
}
int gettc(int i, int j)
{
    if(!i)return TC[j];
    return TC[j]-TC[i-1];
}

int cate(int i, int j)
{
    if(!i)return pepoz[j];
    return pepoz[j]-pepoz[i-1];
}

int gett2(int i, int j)
{
    if(!i)return st2[j];
    return st2[j]-st2[i-1];
}
int getc2(int i, int j)
{
    if(!i)return sc2[j];
    return sc2[j]-sc2[i-1];
}
bool samea(int i, int j)
{
    return geta1(i,j)==geta2(i,j);
}
bool samet(int i, int j)
{
    return gett1(i,j)==gett2(i,j);
}
bool samec(int i, int j)
{
    return getc1(i,j)==getc2(i,j);
}
void init(string a, string b)
{
    int i,n;
  	n=a.length();
    sa1[0]=(a[0]=='A');
    st1[0]=(a[0]=='T');
    sc1[0]=(a[0]=='C');
    for(i=1;i<n;i++)
    {
        sa1[i]=sa1[i-1];
        st1[i]=st1[i-1];
        sc1[i]=sc1[i-1];
        if(a[i]=='A')sa1[i]++;
        else if(a[i]=='T')st1[i]++;
        else sc1[i]++;
    }
    sa2[0]=(b[0]=='A');
    st2[0]=(b[0]=='T');
    sc2[0]=(b[0]=='C');
    pepoz[0]=(a[0]==b[0]);
    i=0;
    if(a[i]=='A')
    {
        if(b[i]=='T')AT[i]++;
        else if(b[i]=='C')AC[i]++;
    }
    if(a[i]=='C')
    {
        if(b[i]=='A')CA[i]++;
        else if(b[i]=='T')CT[i]++;
    }
    if(a[i]=='T')
    {
        if(b[i]=='A')TA[i]++;
        else if(b[i]=='C')TC[i]++;
    }
    for(i=1;i<n;i++)
    {
        sa2[i]=sa2[i-1];
        st2[i]=st2[i-1];
        sc2[i]=sc2[i-1];
        if(b[i]=='A')sa2[i]++;
        else if(b[i]=='T')st2[i]++;
        else sc2[i]++;
        pepoz[i]=pepoz[i-1]+(a[i]==b[i]);
        AT[i]=AT[i-1];
        AC[i]=AC[i-1];
        CA[i]=CA[i-1];
        CT[i]=CT[i-1];
        TA[i]=TA[i-1];
        TC[i]=TC[i-1];
        if(a[i]=='A')
        {
            if(b[i]=='T')AT[i]++;
            else if(b[i]=='C')AC[i]++;
        }
        if(a[i]=='C')
        {
            if(b[i]=='A')CA[i]++;
            else if(b[i]=='T')CT[i]++;
        }
        if(a[i]=='T')
        {
            if(b[i]=='A')TA[i]++;
            else if(b[i]=='C')TC[i]++;
        }
    }
}
int get_distance(int x, int y)
{
    if(!samea(x,y)||!samet(x,y)||!samec(x,y))return -1;
    int swps=0;
    int At,Ac,Ca,Ct,Ta,Tc;
    int mac,mat,mct;
    At=getat(x,y);Ac=getac(x,y);
    Ca=getca(x,y);Ct=getct(x,y);
    Ta=getta(x,y);Tc=gettc(x,y);
    mat=min(At,Ta);
    mac=min(Ac,Ca);
    mct=min(Ct,Tc);
    At-=mat;Ta-=mat;
    Ac-=mac;Ca-=mac;
    Ct-=mct;Tc-=mct;
    swps=mat+mac+mct;
    swps+=2*min({Ac,Ta,Ct});
    swps+=2*min({At,Tc,Ca});
    return swps;
}

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