Submission #446074

#	Time	Username	Problem	Language	Result	Execution time	Memory
446074		boris_mihov	Mutating DNA (IOI21_dna)	C++17	100 / 100	65 ms	9744 KiB

dna

#include <iostream>
using namespace std;
const int maxn = 1e5+10;
int prefix[3][3][maxn], n;
int prefix_letters[2][3][maxn];
int convert[128];

void init(string a, string b) {

    n = a.size();
    convert['A'] = 0;
    convert['C'] = 1;
    convert['T'] = 2;
    a = ' ' + a;
    b = ' ' + b;

    for (int i = 1 ; i <= n ; ++i) {

        for (int x = 0 ; x < 3 ; ++x) {

            prefix_letters[0][x][i] = prefix_letters[0][x][i-1];
            prefix_letters[1][x][i] = prefix_letters[1][x][i-1];

        }

        for (int x = 0 ; x < 3 ; ++x)
            for (int y = 0 ; y < 3 ; ++y)
                prefix[x][y][i] = prefix[x][y][i-1];
            

        ++prefix[convert[a[i]]][convert[b[i]]][i];
        ++prefix_letters[0][convert[a[i]]][i];
        ++prefix_letters[1][convert[b[i]]][i];

    }

}

int t[3][3];

int get_distance(int l, int r) {

    ++l; ++r;

    for (int i = 0 ; i < 3 ; ++i)
        if (prefix_letters[0][i][r] - prefix_letters[0][i][l-1] != prefix_letters[1][i][r] - prefix_letters[1][i][l-1]) return -1; 

    for (int x = 0 ; x < 3 ; ++x)
        for (int y = 0 ; y < 3 ; ++y)
            t[x][y] = prefix[x][y][r] - prefix[x][y][l-1];

    t[0][0] = 0;
    t[1][1] = 0;
    t[2][2] = 0;
    int ans = 0;

    for (int x = 0 ; x < 3 ; ++x) {
        for (int y = x+1 ; y < 3 ; ++y) {

            int remove = min(t[x][y], t[y][x]);
            t[x][y] -= remove;
            t[y][x] -= remove;
            ans += remove;

        }
    }

    for (int x = 0 ; x < 3 ; ++x) {
        for (int y = 0 ; y < 3 ; ++y) {
            if (t[x][y] > 0) {

                ans += t[x][y]*2;
                return ans;

            }
        }
    }

    return ans;

}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:31:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         ++prefix[convert[a[i]]][convert[b[i]]][i];
      |                              ^
dna.cpp:31:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         ++prefix[convert[a[i]]][convert[b[i]]][i];
      |                                             ^
dna.cpp:32:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |         ++prefix_letters[0][convert[a[i]]][i];
      |                                         ^
dna.cpp:33:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |         ++prefix_letters[1][convert[b[i]]][i];
      |                                         ^

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