Submission #684806

#	Time	Username	Problem	Language	Result	Execution time	Memory
684806		acceptify	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	17588 KiB

dna

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

const int mxn = 1e5 + 5;

int mp[205], cnta[mxn][5], cntb[mxn][5], mutate[mxn][5][5];

void init(string a, string b) {
    mp['A'] = 0, mp['T'] = 1, mp['C'] = 2;
    a = " " + a, b = " " + b;
    for (int i = 1; i < a.length(); i++) {
        for (int j = 0; j < 3; j++) {
            cnta[i][j] = cnta[i - 1][j];
            cntb[i][j] = cntb[i - 1][j];
            for (int k = 0; k < 3; k++) mutate[i][j][k] = mutate[i - 1][j][k];
        }
        cnta[i][mp[a[i]]]++;
        cntb[i][mp[b[i]]]++;
        if (a[i] != b[i]) mutate[i][mp[a[i]]][mp[b[i]]]++;
    }
}

int get_distance(int x, int y) {
    y++;
    for (int i = 0; i < 3; i++) if (cnta[y][i] - cnta[x][i] != cntb[y][i] - cntb[x][i]) return -1;
    int a = mutate[y][0][1] - mutate[x][0][1];
    int b = mutate[y][1][0] - mutate[x][1][0];
    int c = mutate[y][0][2] - mutate[x][0][2];
    int d = mutate[y][2][0] - mutate[x][2][0];
    int e = mutate[y][1][2] - mutate[x][1][2];
    int f = mutate[y][2][1] - mutate[x][2][1];
    return min(a, b) + min(c, d) + min(e, f) + (abs(a - b) + abs(c - d) + abs(e - f)) * 2 / 3;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 1; i < a.length(); i++) {
      |                     ~~^~~~~~~~~~~~
dna.cpp:18:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         cnta[i][mp[a[i]]]++;
      |                        ^
dna.cpp:19:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |         cntb[i][mp[b[i]]]++;
      |                        ^
dna.cpp:20:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |         if (a[i] != b[i]) mutate[i][mp[a[i]]][mp[b[i]]]++;
      |                                            ^
dna.cpp:20:54: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |         if (a[i] != b[i]) mutate[i][mp[a[i]]][mp[b[i]]]++;
      |                                                      ^

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