Submission #734496

#	Time	Username	Problem	Language	Result	Execution time	Memory
734496		Roman70	Mutating DNA (IOI21_dna)	C++17	56 / 100	137 ms	211532 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
 
 
using namespace std;
 
string c,d;
 
const int sz = 1e6;
 
   int prefix[sz][26];
   int prefix1[sz][26];
   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: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16