Submission #464943

#	Time	Username	Problem	Language	Result	Execution time	Memory
464943		marko	Mutating DNA (IOI21_dna)	C++17	100 / 100	676 ms	104900 KiB

dna

#include <bits/stdc++.h>

using namespace std;

vector<unordered_map<char, unordered_map<char, int>>> counts {};
vector<unordered_map<char, int>> absolute_counts {};

void init(string a, string b)
{
    const int n = a.size();
    counts.resize(n + 1);

    for (int i = 0; i < n; i++) {
        counts[i + 1] = counts[i];
        counts[i + 1][a[i]][b[i]]++;
    }
}

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

    int ans {};

    auto cnts = counts[y];

    int doubles {};
    for (auto a : { 'A', 'C', 'T' })
        for (auto b : { 'A', 'C', 'T' })
            cnts[a][b] -= counts[x][a][b];

    unordered_map<char, int> counts_a {}, counts_b {};

    for (auto a : { 'A', 'C', 'T' }) {
        for (auto b : { 'A', 'C', 'T' }) {
            counts_a[a] += cnts[a][b];
            counts_b[b] += cnts[a][b];
        }
    }

    for (auto a : { 'A', 'C', 'T' }) {
        if (counts_a[a] != counts_b[a])
            return -1;
    }

    for (auto a : { 'A', 'C', 'T' }) {
        for (auto b : { 'A', 'C', 'T' }) {
            if (b == a)
                continue;
            int take = min(cnts[a][b], cnts[b][a]);
            cnts[a][b]-=take;
            cnts[b][a]-=take;
            doubles += take;
        }
    }

    int triples {};
    for (auto a : { 'A', 'C', 'T' }) {
        for (auto b : { 'A', 'C', 'T' }) {
            if (b == a)
                continue;
            for (auto c : { 'A', 'C', 'T' }) {
                if (c == b || c == a)
                    continue;
                auto &cnts_ab = cnts[a][b];
                auto &cnts_bc = cnts[b][c];
                auto &cnts_ca = cnts[c][a];

                int take = min({ cnts[a][b], cnts[b][c], cnts[c][a] });

                cnts_ab-=take;
                cnts_bc-=take;
                cnts_ca-=take;
                triples += take;
            }
        }
    }

    return triples * 2 + doubles ;
}

// auto main() -> int
// {
//     init("ATACAT", "ACTATA");
//     cout << get_distance(1, 3) << endl;
//     cout << get_distance(4, 5) << endl;
//     cout << get_distance(3, 5) << endl;
// }

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:23:9: warning: unused variable 'ans' [-Wunused-variable]
   23 |     int ans {};
      |         ^~~

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