Submission #571533

#	Time	Username	Problem	Language	Result	Execution time	Memory
571533		il9	Mutating DNA (IOI21_dna)	C++17	100 / 100	60 ms	8584 KiB

dna

#include <bits/stdc++.h>

using namespace std;
int pre[100001][6];
int n;
int q;
int pre1[100001][3][2];
int get_distance(int x,int y)
{
    //pre[y+1]-pre[x]

    int ans[6];
    for(int i=0;i<3;i++)
    {
        if(pre1[y+1][i][0]-pre1[x][i][0]!=pre1[y+1][i][1]-pre1[x][i][1])
        {

            return -1;
        }
    }
    for(int i=0;i<6;i++)
    {
        ans[i]=pre[y+1][i]-pre[x][i];
    }
    int prop=0;
    for(int i=0;i<6;i+=2)
    {
        int temp=min(ans[i],ans[i+1]);
        prop+=temp;

        ans[i]-=temp;
        ans[i+1]-=temp;
    }
    int temp=0;
    for(int i=0;i<6;i++)
    {
        temp+=ans[i];
    }

    if(temp%3==0)
    {
        temp/=3;
        temp*=2;
    }else
    {
        temp=2*(temp/3)+temp%3;
    }

    return prop+temp;
}
void init(string a,string b)
{
    n=a.size();

    for(int i=0;i<6;i++)
    {
        pre[0][i]=0;
    }
    pre1[0][0][0]=0;
    pre1[0][1][0]=0;
    pre1[0][2][0]=0;
      pre1[0][0][1]=0;
    pre1[0][1][1]=0;
    pre1[0][2][1]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            pre1[i+1][j][0]=pre1[i][j][0];
            pre1[i+1][j][1]=pre1[i][j][1];
        }
        if(a[i]=='A')
        {
            pre1[i+1][0][0]++;
        }else if(a[i]=='T')
        {
             pre1[i+1][1][0]++;
        }else
        {
             pre1[i+1][2][0]++;
        }
        if(b[i]=='A')
        {
            pre1[i+1][0][1]++;
        }else if(b[i]=='T')
        {
             pre1[i+1][1][1]++;
        }else
        {
             pre1[i+1][2][1]++;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<6;j++)
        {
            pre[i+1][j]=pre[i][j];
        }
        if(a[i]!=b[i])
        {
            if(a[i]=='A')
            {
                if(b[i]=='T')
                {
                    pre[i+1][0]++;
                }else if(b[i]=='C')
                {
                     pre[i+1][2]++;
                }

            }else if(a[i]=='T')
            {
                if(b[i]=='A')
                {
                    pre[i+1][1]++;
                }else if(b[i]=='C')
                {
                    pre[i+1][5]++;
                }
            }else if(a[i]=='C')
            {
                if(b[i]=='T')
                {
                    pre[i+1][4]++;
                }else if(b[i]=='A')
                {
                    pre[i+1][3]++;
                }
            }
        }
    }

}

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