Submission #1040398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040398		yanb	Mutating DNA (IOI21_dna)	C++17	0 / 100	1596 ms	15964 KiB

dna

#include <bits/stdc++.h>
    
using namespace std;
    
#define int long long
#define pii pair<long long, long long>

string a, b;
map<string, vector<int>> pref;
map<char, vector<int>> apref, bpref;

void init(string a_, string b_) {
    a = a_, b = b_;
    int n = a.size();
    string possible = "ACT";
    for (char c1 : possible) {
        for (char c2 : possible) {
            string t = ""; t += c1; t += c2;
            pref[t].resize(n + 1);
        }
        apref[c1].resize(n + 1);
        bpref[c1].resize(n + 1);
    }

    for (int i = 0; i < n; i++) {
        for (auto [str, vec] : pref) {
            string t = ""; t += a[i]; t += b[i];
            pref[str][i + 1] = pref[str][i] + (t == str);
        }
        for (auto [chr, vec] : apref) {
            apref[chr][i + 1] = apref[chr][i] + (a[i] == chr);
        }
        for (auto [chr, vec] : bpref) {
            bpref[chr][i + 1] = bpref[chr][i] + (b[i] == chr);
        }
    }

    /*for (auto [str, vec] : apref) {
        cout << str << ": ";
        for (int x : vec) cout << x << " ";
        cout << "\n";
    }*/
}

int get_distance(signed l, signed r) {
    map<string, int> cnt;
    map<char, int> acnt, bcnt;
    for (auto [str, vec] : pref) {
        cnt[str] = vec[r + 1] - vec[l];
    }
    for (auto [chr, vec] : apref) {
        acnt[chr] = vec[r + 1] - vec[l];
    }
    for (auto [chr, vec] : bpref) {
        bcnt[chr] = vec[r + 1] - vec[l];
    }

    for (auto [chr, _] : acnt) {
        //cout << chr << ": " << acnt[chr] << " " << bcnt[chr] << "\n";
        if (acnt[chr] != bcnt[chr])
            return -1;
    }

    int atflip = min(cnt["TA"], cnt["AT"]);
    int acflip = min(cnt["CA"], cnt["AC"]);
    int ctflip = min(cnt["TC"], cnt["CT"]);
    int ans = atflip + acflip + ctflip;
    cnt["TA"] -= atflip;
    cnt["AT"] -= atflip;
    cnt["TC"] -= ctflip;
    cnt["CT"] -= ctflip;
    cnt["CA"] -= acflip;
    cnt["AC"] -= acflip;
    ans += (cnt["TA"] + cnt["AT"] + cnt["TC"] + cnt["CT"] + cnt["CA"] + cnt["AC"]) / 3 * 2;

    return ans;
}

#ifdef ONLINE_JUDGE
signed main() {
    init("ATACAT", "ACTATA");
    cout << get_distance(1, 3) << "\n";
    cout << get_distance(4, 5) << "\n";
    cout << get_distance(3, 5) << "\n";
}
#endif

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