Submission #1201782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201782		12baater	Mutating DNA (IOI21_dna)	C++20	100 / 100	308 ms	115440 KiB

dna

#include <iostream>
// #include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;

vector<map<string, int> > prefPairs {
    {
        {"AA", 0},
        {"AC", 0},
        {"AT", 0},
        {"CC", 0},
        {"CA", 0},
        {"CT", 0},
        {"TT", 0},
        {"TA", 0},
        {"TC", 0}
    }
};

vector<map<char, int> > prefA = {{
    {'A', 0},
    {'C', 0},
    {'T', 0},
}};

vector<map<char, int> > prefB = {{
    {'A', 0},
    {'C', 0},
    {'T', 0},
}};

void init(string a, string b) {
    prefA[0][a[0]]++;
    prefB[0][b[0]]++;
    string s;
    s += a[0];
    s += b[0];
    prefPairs[0][s]++;
    for(int i = 1; i < a.size(); i++) {
        prefA.push_back(prefA[i-1]);
        prefA[i][a[i]]++;
        prefB.push_back(prefB[i-1]);
        prefB[i][b[i]]++;
        prefPairs.push_back(prefPairs[i-1]);
        s = "";
        s += a[i];
        s += b[i];
        prefPairs[i][s]++;
    }
}

int get_distance(int x, int y) {
    for (const auto& [key,value] : prefA[0]) {
        if(x > 0) {
            if (prefA[y][key] - prefA[x-1][key] != prefB[y][key] - prefB[x-1][key]) return -1;
            continue;
        }
        if (prefA[y][key] != prefB[y][key]) return -1;
    }

    int moves = 0;

    map<string,int> current = prefPairs[y];
    if(x > 0) {
        for(const auto& [key,value] : prefPairs[x-1]) {
            current[key] -= value;
        }
    }

    int total = 0;
    for(const auto& [key,value] : current) {
        if (key == "AA" || key == "CC" || key == "TT") continue;
        total += value;
    }


    total -= 2 * min(current["AC"], current["CA"]);
    moves += min(current["AC"], current["CA"]);

    total -= 2 * min(current["AT"], current["TA"]);
    moves += min(current["AT"], current["TA"]);

    total -= 2 * min(current["CT"], current["TC"]);
    moves += min(current["CT"], current["TC"]);

    moves += (total/3)*2;
    total %= 3;

    if (total == 1) {
        return -1;
       // cout << "Not good" << endl;
    }
    if(total) {
        moves++;
    }
    return moves;
}

/*
int main() {
    int n, q; cin >> n >> q;
    string a, b; cin >> a >> b;
    init(a,b);
    cout << get_distance(1, 2) << endl;

    for(const auto& m : prefPairs) {
        for(const auto& [key,value] : m) {
            cout << key << " " << value << endl;
        }
        cout << "\n\n\n\n";
    }

    return 0;
}
*/

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