Submission #1281065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281065		david_g611	Mutating DNA (IOI21_dna)	C++20	100 / 100	25 ms	4852 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

const int NMAX=1e5;
int n, ab[NMAX+1], ba[NMAX+1], bc[NMAX+1], cb[NMAX+1], ac[NMAX+1], ca[NMAX+1];

void init(string a, string b)
{
    n=a.size();
    for(int i=1; i<=n; i++)
    {
        char c1=a[i-1], c2=b[i-1];
        ab[i]=ab[i-1];ac[i]=ac[i-1];bc[i]=bc[i-1];
        ba[i]=ba[i-1];ca[i]=ca[i-1];cb[i]=cb[i-1];
        if(c1=='A' && c2=='T')ab[i]++;
        if(c1=='A' && c2=='C')ac[i]++;
        if(c1=='T' && c2=='C')bc[i]++;
        if(c1=='T' && c2=='A')ba[i]++;
        if(c1=='C' && c2=='A')ca[i]++;
        if(c1=='C' && c2=='T')cb[i]++;
    }
}

int get_distance(int x, int y)
{
    ++x, ++y;

    int ans=0;
    int nr_ab=ab[y]-ab[x-1], nr_ba=ba[y]-ba[x-1];
    int nr_bc=bc[y]-bc[x-1], nr_cb=cb[y]-cb[x-1];
    int nr_ac=ac[y]-ac[x-1], nr_ca=ca[y]-ca[x-1];

    if(nr_ab >= nr_ba)
    {
        ans=nr_ba+nr_cb+nr_ac;
        if(nr_ab-nr_ba != nr_bc-nr_cb || nr_ab-nr_ba != nr_ca-nr_ac)
            return -1;
        else
            return ans+2*(nr_ab-nr_ba);
    }
    else
    {
        ans=nr_ab+nr_bc+nr_ca;
        if(nr_ba-nr_ab != nr_cb-nr_bc || nr_ba-nr_ab != nr_ac-nr_ca)
            return -1;
        else
            return ans+2*(nr_ba-nr_ab);
    }
}

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