Submission #877582

#	Time	Username	Problem	Language	Result	Execution time	Memory
877582		tigar	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	7560 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)
{
    for(int i=0; i<a.size(); i++)
    {
        ca[i+1]=ca[i]; ac[i+1]=ac[i]; ba[i+1]=ba[i];
        ab[i+1]=ab[i]; cb[i+1]=cb[i]; bc[i+1]=bc[i];
        aa[i+1]=aa[i]; bb[i+1]=bb[i]; cc[i+1]=cc[i];
        if(a[i]=='A' and b[i]=='T')ab[i+1]++;
        if(a[i]=='A' and b[i]=='C')ac[i+1]++;
        if(a[i]=='T' and b[i]=='C')bc[i+1]++;
        if(a[i]=='C' and b[i]=='T')cb[i+1]++;
        if(a[i]=='T' and b[i]=='A')ba[i+1]++;
        if(a[i]=='C' and b[i]=='A')ca[i+1]++;
        if(a[i]=='A' and b[i]=='A')aa[i+1]++;
        if(a[i]=='T' and b[i]=='T')bb[i+1]++;
        if(a[i]=='C' and b[i]=='C')cc[i+1]++;
    }
}

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

int get_distance(int x, int y)
{
    x++; 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;
}

/*int main()
{
    string a, b;
    cin>>a>>b;
    init(a, b);
    int q;cin>>q;
    while(q--)
    {
        int x, y; cin>>x>>y;
        cout<<get_distance(x, y)<<endl;
    }
}*/

Compilation message (stderr)

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

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