Submission #647127

#	Time	Username	Problem	Language	Result	Execution time	Memory
647127		kkkkkkkk	Mutating DNA (IOI21_dna)	C++17	56 / 100	40 ms	6840 KiB

dna

#include "dna.h"
#include <iostream>
 
using namespace std;
 
string a,b;
int klk_A1[100001]={0},klk_C1[100001]={0},klk_T1[100001]={0};
int klk_A2[100001]={0},klk_C2[100001]={0},klk_T2[100001]={0};
int razlicni[100001]={0};
 
void init(string A,string B)
{
    a=A;
    b=B;
    if (a[0]=='A') klk_A1[0]=1;
    else if (a[0]=='C') klk_C1[0]=1;
    else klk_T1[0]=1;
    if (b[0]=='A') klk_A2[0]=1;
    else if (b[0]=='C') klk_C2[0]=1;
    else klk_T2[0]=1;
    if (a[0]!=b[0]) razlicni[0]=1;
    for (int i=1;i<a.size();i++)
    {
        klk_A1[i]=klk_A1[i-1],klk_C1[i]=klk_C1[i-1],klk_T1[i]=klk_T1[i-1];
        if (a[i]=='A') klk_A1[i]++;
        else if (a[i]=='C') klk_C1[i]++;
        else klk_T1[i]++;
        klk_A2[i]=klk_A2[i-1],klk_C2[i]=klk_C2[i-1],klk_T2[i]=klk_T2[i-1];
        if (b[i]=='A') klk_A2[i]++;
        else if (b[i]=='C') klk_C2[i]++;
        else klk_T2[i]++;
        razlicni[i]=razlicni[i-1];
        if (a[i]!=b[i]) razlicni[i]++;
    }  
}
 
int get_distance(int x,int y)
{
    bool ok=false;
    if (x==0&&klk_A1[y]==klk_A2[y]&&klk_C1[y]==klk_C2[y]&&klk_T1[y]==klk_T2[y])
        ok=true;
    if (x>0&&klk_A1[y]-klk_A1[x-1]==klk_A2[y]-klk_A2[x-1]&&klk_C1[y]-klk_C1[x-1]==klk_C2[y]-klk_C2[x-1]&&klk_T1[y]-klk_T1[x-1]==klk_T2[y]-klk_T2[x-1])
        ok=true;
    if (!ok) return -1;
    if (y-x<=2)
    {
        string a1,b1;
        for (int i=x;i<=y;i++)
        {
            a1+=a[i];
            b1+=b[i];
        }
        int br=0;
        for (int i=0;i<a1.size();i++)
            if (a1[i]!=b1[i]) br++;
        if (br==0) return 0;
        return br-1;
    }
    else
    {
        int razl=0;
        if (x==0) razl=razlicni[y];
        else razl=razlicni[y]-razlicni[x-1];
        return razl/2;
    }
}

Compilation message (stderr)

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

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