Submission #1000176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000176		y_combinator	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	7180 KiB

dna

#include <algorithm>
#include <array>
#include <string>
#include <vector>

auto pfxs = std::vector<std::array<std::array<int, 3>, 3>>();

auto get_distance(int x, int y) -> int {

    auto cnts = std::array<std::array<int, 3>, 3>();
    auto diffs = std::array<int, 3>();

    for (auto i = 0; i < 3; ++i) {
        for (auto j = 0; j < 3; ++j) {
            cnts[i][j] = pfxs[y + 1][i][j] - pfxs[x][i][j];
            diffs[i] += cnts[i][j];
            diffs[j] -= cnts[i][j];
        }
    }

    if (std::count(std::begin(diffs), std::end(diffs), 0) < 3) {
        return -1;
    }

    auto dist = 0;
    auto rem = 0;

    for (auto i = 0; i < 3; ++i) {
        for (auto j = i + 1; j < 3; ++j) {
            const auto mn = std::min(cnts[i][j], cnts[j][i]);
            dist += mn;
            cnts[i][j] -= mn;
            cnts[j][i] -= mn;
            rem += cnts[i][j] + cnts[j][i];
        }
    }

    dist += rem / 3 * 2;

    return dist;

}

auto init(std::string a, std::string b) {

    const auto n = static_cast<int>(std::size(a));

    pfxs.resize(n + 1);

    for (auto i = 0; i < n; ++i) {
        pfxs[i + 1] = pfxs[i];
        const auto conv = [](char type) {
            if (type == 'A') {
                return 0;
            }
            return type == 'C' ? 1 : 2;
        };
        ++pfxs[i + 1][conv(a[i])][conv(b[i])];
    }

}

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