Submission #1203776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203776		simona1230	Mutating DNA (IOI21_dna)	C++20	21 / 100	22 ms	8772 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int p1[maxn][3];
int p2[maxn][3];
int p3[maxn][3][3];
int s1[maxn];
int s2[maxn];
void init(std::string a, std::string b)
{
    memset(p1,0,sizeof(p1));
    memset(p2,0,sizeof(p2));
    memset(p3,0,sizeof(p3));
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='A')s1[i]=0;
        else if(a[i]=='C')s1[i]=1;
        else s1[i]=2;

        if(b[i]=='A')s2[i]=0;
        else if(b[i]=='C')s2[i]=1;
        else s2[i]=2;
    }

    p1[0][s1[0]]++;
    p2[0][s2[0]]++;
    p3[0][s1[0]][s2[0]]++;
    for(int i=1;i<a.size();i++)
    {
        for(int t1=0;t1<=2;t1++)
        {
            for(int t2=0;t2<=2;t2++)
            {
                p3[i][t1][t2]=p3[i-1][t1][t2];
            }
            p1[i][t1]=p1[i-1][t1];
            p2[i][t1]=p2[i-1][t1];
        }

        p3[i][s1[i]][s2[i]]++;
        p1[i][s1[i]]++;
        p2[i][s2[i]]++;
    }
}

int c[3][3];

int get_distance(int x, int y)
{
    if(x==0&&(p1[y][0]!=p2[y][0]||p1[y][1]!=p2[y][1]||p1[y][2]!=p2[y][2])|| x!=0&&
       (p1[y][0]-p1[x-1][0]!=p2[y][0]-p2[x-1][0]||p1[y][1]-p1[x-1][1]!=p2[y][1]-p2[x-1][1]||p1[y][2]-p1[x-1][2]!=p2[y][2]-p2[x-1][2]))return -1;

    for(int i=0;i<=2;i++)
    {
        for(int j=0;j<=2;j++)
        {
            if(x==0)c[i][j]=p3[y][i][j];
            else c[i][j]=p3[y][i][j]-p3[x-1][i][j];
        }
    }

    int ans=0;
    int all=y-x+1;
    all-=c[0][0];
    all-=c[1][1];
    all-=c[2][2];
    int h=min(c[0][1],c[1][0]);
    ans+=h;
    all-=h;
    h=min(c[0][2],c[2][0]);
    ans+=h;
    all-=h;
    h=min(c[1][2],c[2][1]);
    ans+=h;
    all-=h;
    ans+=(all/3)*2;

	return ans;
}

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