Submission #539090

#	Time	Username	Problem	Language	Result	Execution time	Memory
539090		groshi	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	8584 KiB

dna

#include<iostream>
#include<map>
using namespace std;
map<char,int> rodzaj;
int x0[200000][3];
int y0[200000][3];
int roz01[100010];
int roz10[100010];
int roz02[100010];
int roz20[100010];
int roz12[100010];
int roz21[100010];
void init(string x,string y)
{
    rodzaj['A']=0;
    rodzaj['C']=1;
    rodzaj['T']=2;
    for(int i=0;i<x.length();i++)
    {
        x0[i+1][0]=x0[i][0];
        x0[i+1][1]=x0[i][1];
        x0[i+1][2]=x0[i][2];
        x0[i+1][rodzaj[x[i]]]++;
    }
    for(int i=0;i<y.length();i++)
    {
        y0[i+1][0]=y0[i][0];
        y0[i+1][1]=y0[i][1];
        y0[i+1][2]=y0[i][2];
        y0[i+1][rodzaj[y[i]]]++;
    }
    for(int i=0;i<x.length();i++)
    {
        roz01[i+1]=roz01[i];
        roz02[i+1]=roz02[i];
        roz10[i+1]=roz10[i];
        roz12[i+1]=roz12[i];
        roz20[i+1]=roz20[i];
        roz21[i+1]=roz21[i];
        if(x[i]==y[i])
            continue;
        if(x[i]=='A' && y[i]=='C')
            roz01[i+1]++;
        if(x[i]=='C' && y[i]=='A')
            roz10[i+1]++;
        if(x[i]=='A' && y[i]=='T')
            roz02[i+1]++;
        if(x[i]=='T' && y[i]=='A')
            roz20[i+1]++;
        if(x[i]=='C' && y[i]=='T')
            roz12[i+1]++;
        if(x[i]=='T' && y[i]=='C')
            roz21[i+1]++;
    }
}
int get_distance(int x,int y)
{
    for(int i=0;i<3;i++)
        if(x0[y+1][i]-x0[x][i]!=y0[y+1][i]-y0[x][i])
            return -1;
    int wynik=0;
    int ile_01=roz01[y+1]-roz01[x];
    int ile_02=roz02[y+1]-roz02[x];
    int ile_12=roz12[y+1]-roz12[x];
    int ile_10=roz10[y+1]-roz10[x];
    int ile_20=roz20[y+1]-roz20[x];
    int ile_21=roz21[y+1]-roz21[x];
    wynik+=min(ile_01,ile_10)+min(ile_02,ile_20)+min(ile_12,ile_21);
    ile_01=max(ile_01,ile_10)-min(ile_01,ile_10);
    ile_02=max(ile_02,ile_20)-min(ile_02,ile_20);
    ile_12=max(ile_12,ile_21)-min(ile_12,ile_21);
    wynik+=((ile_01+ile_02+ile_12)/3)*2;
    return wynik;
}

Compilation message (stderr)

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

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