Submission #734490

#	Time	Username	Problem	Language	Result	Execution time	Memory
734490		Roman70	Mutating DNA (IOI21_dna)	C++17	0 / 100	274 ms	424980 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>

 
using namespace std;
 
string c,d;

const int sz = 1e6;

   int prefix[26][sz];
   int prefix1[26][sz];
   int prefix2[sz];
 
void init(string a,string b) {
    c = a;
    d = b;




    memset(prefix,0,sizeof(prefix));
    memset(prefix1,0,sizeof(prefix1));
    memset(prefix2,0,sizeof(prefix2));


    prefix[0][c[0] - 'A']++;
    prefix1[0][d[0] - 'A']++;


    // 65 67 84

    if(c[0] != d[0]) prefix2[0]++;



    for(int i = 1;i<c.size();i++){

         prefix[i][c[i] - 'A']++;

        prefix[i][0]+= prefix[i-1][0];

        prefix[i][2]+= prefix[i-1][2];

        prefix[i][19]+= prefix[i-1][19];

        if(c[i] != d[i]) prefix2[i]++;
        prefix2[i] += prefix2[i-1];


    }

    for(int i = 1;i<d.size();i++){

         prefix1[i][d[i] - 'A']++;

        prefix1[i][0]+= prefix1[i-1][0];

        prefix1[i][2]+= prefix1[i-1][2];

        prefix1[i][19]+= prefix1[i-1][19];

    }

}
 
int get_distance(int x,int y){
   
    int ans;

    int cmp[2][26];



    cmp[0][0] = prefix[y][0] - (x == 0 ? 0 : prefix[x-1][0]);


    cmp[0][2]=  prefix[y][2] - (x == 0 ? 0 : prefix[x-1][2]);
    cmp[0][19]=  prefix[y][19] - (x == 0 ? 0 : prefix[x-1][19]);
    cmp[1][0]=  prefix1[y][0] - (x == 0 ? 0 : prefix1[x-1][0]);
    cmp[1][2]=  prefix1[y][2] - (x == 0 ? 0 : prefix1[x-1][2]);
    cmp[1][19]=  prefix1[y][19] - (x == 0 ? 0 : prefix1[x-1][19]);




    if(cmp[0][0] == cmp[1][0] && cmp[0][2] == cmp[1][2] && cmp[0][19] == cmp[1][19]) ans = (prefix2[y] - (x == 0 ? 0 : prefix2[x-1])) / 2 + ((prefix2[y] - (x == 0 ? 0 : prefix2[x-1])) % 2);
    else ans = -1;


    return ans;

}

Compilation message (stderr)

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

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