Submission #703862

#	Time	Username	Problem	Language	Result	Execution time	Memory
703862		NourWael	Mutating DNA (IOI21_dna)	C++17	100 / 100	38 ms	8968 KiB

dna

#include <iostream>
#include <bits/stdc++.h>
#include "dna.h";
typedef long long ll;
using namespace std;

const int mxN=1e5+5;
int d[100005];
int numbersA[mxN][3], numbersB[mxN][3];
int n,q,x,y;
string f,s;
int aa=0, ta=0, ca=0,ab=0, tb=0, cb=0, difference=0;
int rat=0, rta=0, rac=0,rca=0, rtc=0, rct=0;

vector<pair<int,int>>replaceA (mxN,{0,0});
vector<pair<int,int>>replaceT (mxN,{0,0});
vector<pair<int,int>>replaceC (mxN,{0,0});
void init(string a, string b)
{

    for(int i=0; i<a.size(); i++)
    {
        if(a[i]!=b[i])
        {
            difference++;
        }
        d[i]=difference;

        if(a[i]=='A')
        {
            aa++;
            if(b[i]=='T') rat++;
            if(b[i]=='C') rac++;
        }
        else if (a[i]=='T')
        {
            ta++;
             if(b[i]=='A') rta++;
             if(b[i]=='C') rtc++;
        }
        else if (a[i]=='C')
        {
            ca++;
            if(b[i]=='A') rca++;
            if(b[i]=='T') rct++;
        }
        numbersA[i][0]=aa;
        numbersA[i][1]=ta;
        numbersA[i][2]=ca;

        replaceA[i].first=rat;
        replaceA[i].second=rac;
        replaceT[i].first=rta;
        replaceT[i].second=rtc;
        replaceC[i].first=rca;
        replaceC[i].second=rct;


        if(b[i]=='A')
        {
            ab++;
        }
        else if (b[i]=='T')
        {
            tb++;
        }
        else if (b[i]=='C')
        {
            cb++;
        }
        numbersB[i][0]=ab;
        numbersB[i][1]=tb;
        numbersB[i][2]=cb;
    }

}

int get_distance(int x,int y)
{
    int ans=0;
    int div=d[y];
    int da1=numbersA[y][0], dt1=numbersA[y][1], dc1=numbersA[y][2], da2=numbersB[y][0], dt2=numbersB[y][1], dc2=numbersB[y][2] ;
    int rati=replaceA[y].first, rtai=replaceT[y].first, raci=replaceA[y].second, rcai=replaceC[y].first, rtci=replaceT[y].second, rcti=replaceC[y].second;

    if(x!=0)
    {
        div-=d[x-1];

        da1-=numbersA[x-1][0];
        dt1-=numbersA[x-1][1];
        dc1-=numbersA[x-1][2];
        da2-=numbersB[x-1][0];
        dt2-=numbersB[x-1][1];
        dc2-=numbersB[x-1][2];
        rati-=replaceA[x].first;
        rtai-=replaceT[x].first;
        raci-=replaceA[x].second;
        rcai-=replaceC[x].first;
        rtci-=replaceT[x].second;
        rcti-=replaceC[x].second;
    }


    if(da1==da2 && dt1==dt2 && dc1==dc2)
    {


       ans+=min(rati,rtai);
       div-=(min(rati,rtai))*2;


       ans+=min(raci,rcai);
       div-=(min(raci,rcai))*2;


       ans+=min(rtci,rcti);
       div-=(min(rtci,rcti))*2;

       if(div>1)
       {
           ans+=(div*2)/3;
       }

       return ans;
    }
    else
    {
        return -1;
    }
}

Compilation message (stderr)

dna.cpp:3:17: warning: extra tokens at end of #include directive
    3 | #include "dna.h";
      |                 ^
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     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