Submission #1105793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105793		test00	Mutating DNA (IOI21_dna)	C++17	100 / 100	38 ms	12364 KiB

dna

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

const int MAX = 1e5 + 2;

long long prea[MAX],prec[MAX],pret[MAX],prea1[MAX],prec1[MAX],pret1[MAX],preac[MAX],preat[MAX],preca[MAX],prect[MAX],preta[MAX],pretc[MAX];
string aa, bb;

void init(string a, string b)
{
    int n = a.size();

    aa = "#" + a, bb = "#" + b;

    for(long long i=1; i<=n; i++)
    {
        prea[i]=prea[i-1];
        prec[i]=prec[i-1];
        pret[i]=pret[i-1];
        prea1[i]=prea1[i-1];
        prec1[i]=prec1[i-1];
        pret1[i]=pret1[i-1];
        preac[i]=preac[i-1];
        prect[i]=prect[i-1];
        preta[i]=preta[i-1];
        preat[i]=preat[i-1];
        preca[i]=preca[i-1];
        pretc[i]=pretc[i-1];
        if(aa[i]=='A')
        { prea[i]++; }
        else
            if(aa[i]=='C')
            { prec[i]++; }
            else
            { pret[i]++; }


        if(bb[i]=='A')
        { prea1[i]++; }
        else
            if(bb[i]=='C')
            { prec1[i]++; }
            else
            { pret1[i]++; }

        if(aa[i]=='A'&&bb[i]=='T')
        {
            preat[i]++;
        }
        else
            if(aa[i]=='A'&&bb[i]=='C')
            {
                preac[i]++;
            }
            else
                if(aa[i]=='C'&&bb[i]=='T')
                {
                    prect[i]++;
                }
                else
                    if(aa[i]=='C'&&bb[i]=='A')
                    {
                        preca[i]++;
                    }
                    else
                        if(aa[i]=='T'&&bb[i]=='C')
                        {
                            pretc[i]++;
                        }
                        else
                            if(aa[i]=='T'&&bb[i]=='A')
                            {
                                preta[i]++;
                            }
    }
}
int get_distance(int p,int q)
{
    int x, y;
    x = p+1, y = q+1;

    if(prea[y]-prea[x-1]!=prea1[y]-prea1[x-1])
    {
        return -1;
    }
    if(prec[y]-prec[x-1]!=prec1[y]-prec1[x-1])
    {
        return -1;
    }
    if(pret[y]-pret[x-1]!=pret1[y]-pret1[x-1])
    {
        return -1;
    }

    int ans=0;
    ans+=min(preat[y]-preat[x-1],preta[y]-preta[x-1]);
    ans+=min(preca[y]-preca[x-1],preac[y]-preac[x-1]);
    ans+=min(prect[y]-prect[x-1],pretc[y]-pretc[x-1]);
    ans+=2*(max(preca[y]-preca[x-1],preac[y]-preac[x-1])-min(preca[y]-preca[x-1],preac[y]-preac[x-1]));
    return ans;
}

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