Submission #609164

#	Time	Username	Problem	Language	Result	Execution time	Memory
609164		lorenzoferrari	Mutating DNA (IOI21_dna)	C++17	100 / 100	52 ms	7244 KiB

dna

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

using mat = array<array<int, 3>, 3>;

const string alfa = "ATC";

int n;
vector<mat> prf;

void init(string a, string b) {
    n = a.size();
    prf.resize(n+1);
    for (int i = 0; i < n; ++i) {
        prf[i+1] = prf[i];
        int ca = alfa.find(a[i]);
        int cb = alfa.find(b[i]);
        ++prf[i+1][ca][cb];
    }
}

int get_distance(int x, int y) {
    mat m;
    array<int, 3> sum_row{};
    array<int, 3> sum_col{};
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
        m[i][j] = prf[y+1][i][j] - prf[x][i][j];
        sum_row[i] += m[i][j];
        sum_col[j] += m[i][j];
    }
    if (sum_row != sum_col) return -1;
    int ans = 0;
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) {
        if (i == j) continue;
        int v = min(m[i][j], m[j][i]);
        ans += v;
        m[i][j] -= v;
        m[j][i] -= v;
    }
    ans += 2 * m[0][1];
    ans += 2 * m[1][0];
    return ans;
}

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