Submission #877163

#	Time	Username	Problem	Language	Result	Execution time	Memory
877163		tigar	Mutating DNA (IOI21_dna)	C++17	0 / 100	27 ms	6996 KiB

dna

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

using namespace std;

int ac[100010], ca[100010], ab[100010], ba[100010], bc[100010], cb[100010], aa[100010], bb[100010], cc[100010];

void init(string a, string b)
{
    if(a[0]=='a' and b[0]=='b')ab[0]++;
    if(a[0]=='a' and b[0]=='c')ac[0]++;
    if(a[0]=='b' and b[0]=='c')bc[0]++;
    if(a[0]=='c' and b[0]=='b')cb[0]++;
    if(a[0]=='b' and b[0]=='a')ba[0]++;
    if(a[0]=='c' and b[0]=='a')ca[0]++;
    if(a[0]=='a' and b[0]=='a')aa[0]++;
    if(a[0]=='b' and b[0]=='b')bb[0]++;
    if(a[0]=='c' and b[0]=='c')cc[0]++;

    for(int i=1; i<a.size(); i++)
    {
        ca[i]=ca[i-1]; ac[i]=ac[i-1]; ba[i]=ba[i-1];
        ab[i]=ab[i-1]; cb[i]=cb[i-1]; bc[i]=bc[i-1];
        aa[i]=aa[i-1]; bb[i]=bb[i-1]; cc[i]=cc[i-1];
        if(a[i]=='a' and b[i]=='b')ab[i]++;
        if(a[i]=='a' and b[i]=='c')ac[i]++;
        if(a[i]=='b' and b[i]=='c')bc[i]++;
        if(a[i]=='c' and b[i]=='b')cb[i]++;
        if(a[i]=='b' and b[i]=='a')ba[i]++;
        if(a[i]=='c' and b[i]=='a')ca[i]++;
        if(a[i]=='a' and b[i]=='a')aa[i]++;
        if(a[i]=='b' and b[i]=='b')bb[i]++;
        if(a[i]=='c' and b[i]=='c')cc[i]++;
    }
}

int calc(int *niz, int x, int y)
{
    return niz[y]-niz[x-1];
}

int get_distance(int x, int y)
{
    if(calc(ab, x, y)+calc(ac, x, y)!=calc(ba, x, y)+calc(ca, x, y))return -1;
    if(calc(ab, x, y)+calc(cb, x, y)!=calc(ba, x, y)+calc(bc, x, y))return -1;
    if(calc(bc, x, y)+calc(ac, x, y)!=calc(cb, x, y)+calc(ca, x, y))return -1;
    int dist=y-x+1;
    dist-=calc(aa, x, y);
    dist-=calc(bb, x, y);
    dist-=calc(cc, x, y);
    int BA=calc(ba, x, y), AB=calc(ab, x, y), BC=calc(bc, x, y), CB=calc(cb, x, y), CA=calc(ca, x, y), AC=calc(ac, x, y);
    int cyc1=min(AB, BA);
    AB-=cyc1; BA-=cyc1; dist-=cyc1;
    int cyc2=min(AC, CA);
    AC-=cyc2; CA-=cyc2; dist-=cyc2;
    int cyc3=min(BC, CB);
    CB-=cyc3; BC-=cyc3; dist-=cyc3;
    if(AB!=BC or BC!=CA or CA!=AB)return -1;
    else dist-=AB;
    if(BA!=AC or AC!=CB or CB!=BA)return -1;
    else dist-=BA;
    return dist;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=1; i<a.size(); i++)
      |                  ~^~~~~~~~~

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