Submission #575108

#	Time	Username	Problem	Language	Result	Execution time	Memory
575108		four_specks	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	10628 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

inline namespace tc
{
} // namespace tc

namespace
{
    array<vector<int>, 3> pref_a, pref_b;
    vector<int> diff;
    array<array<vector<int>, 3>, 3> cnt;

} // namespace

const map<char, int> mp = {{pair('A', 0), pair('T', 1), pair('C', 2)}};

void init(string a, string b)
{
    int n = (int)a.length();
    pref_a.fill(vector<int>(n + 1, 0)), pref_b.fill(vector<int>(n + 1, 0));
    diff = vector<int>(n + 1, 0);
    for (int c = 0; c < 3; c++)
        cnt[c].fill(vector<int>(n + 1, 0));
    for (int i = 0; i < n; i++)
    {
        for (int c = 0; c < 3; c++)
        {
            pref_a[c][i + 1] = pref_a[c][i], pref_b[c][i + 1] = pref_b[c][i];
            for (int d = 0; d < 3; d++)
                cnt[c][d][i + 1] = cnt[c][d][i];
        }
        pref_a[mp.at(a[i])][i + 1]++, pref_b[mp.at(b[i])][i + 1]++;
        diff[i + 1] = diff[i] + (a[i] != b[i]);
        cnt[mp.at(a[i])][mp.at(b[i])][i + 1]++;
    }
}

int get_distance(int x, int y)
{
    ++y;

    bool ok = 1;
    for (int c = 0; c < 3; c++)
        ok &= pref_a[c][y] - pref_a[c][x] == pref_b[c][y] - pref_b[c][x];

    if (ok)
    {
        int res = 0;
        int rem = diff[y] - diff[x];
        for (int c = 0; c < 3; c++)
        {
            for (int d = c + 1; d < 3; d++)
            {
                int k = min(cnt[c][d][y] - cnt[c][d][x], cnt[d][c][y] - cnt[d][c][x]);
                res += k;
                rem -= 2 * k;
            }
        }
        assert(rem % 3 == 0);
        res += rem / 3 * 2;
        return res;
    }
    return -1;
}

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