Submission #647177

#	Time	Username	Problem	Language	Result	Execution time	Memory
647177		kkkkkkkk	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	8908 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 A_C[100001]={0},A_T[100001]={0},C_A[100001]={0},C_T[100001]={0},T_A[100001]={0},T_C[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;
    if (a[0]=='A'&&b[0]=='C') A_C[0]++;
    else if (a[0]=='A'&&b[0]=='T') A_T[0]++;
    else if (a[0]=='C'&&b[0]=='A') C_A[0]++;
    else if (a[0]=='C'&&b[0]=='T') C_T[0]++;
    else if (a[0]=='T'&&b[0]=='A') T_A[0]++;
    else if (a[0]=='T'&&b[0]=='C') T_C[0]++;
    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]++;
        A_C[i]=A_C[i-1],A_T[i]=A_T[i-1],C_A[i]=C_A[i-1],C_T[i]=C_T[i-1],T_A[i]=T_A[i-1],T_C[i]=T_C[i-1];
        if (a[i]=='A'&&b[i]=='C') A_C[i]++;
        else if (a[i]=='A'&&b[i]=='T') A_T[i]++;
        else if (a[i]=='C'&&b[i]=='A') C_A[i]++;
        else if (a[i]=='C'&&b[i]=='T') C_T[i]++;
        else if (a[i]=='T'&&b[i]=='A') T_A[i]++;
        else if (a[i]=='T'&&b[i]=='C') T_C[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;
    int ac,at,ca,ct,ta,tc;
    if (x==0) ac=A_C[y],at=A_T[y],ca=C_A[y],ct=C_T[y],ta=T_A[y],tc=T_C[y];
    else ac=A_C[y]-A_C[x-1],at=A_T[y]-A_T[x-1],ca=C_A[y]-C_A[x-1],ct=C_T[y]-C_T[x-1],ta=T_A[y]-T_A[x-1],tc=T_C[y]-T_C[x-1];
    int br_zameni=0,mac=min(ac,ca),mat=min(at,ta),mct=min(ct,tc);
    
    br_zameni+=mac,ac-=mac,ca-=mac;
    br_zameni+=mat,at-=mat,ta-=mat;
    br_zameni+=mct,ct-=mct,tc-=mct;
    br_zameni+=(((ac+at+ca+ct+ta+tc)/3)*2);
    return br_zameni;
    
}

Compilation message (stderr)

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

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