Submission #1160260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160260		JahonaliX	Mutating DNA (IOI21_dna)	C++20	100 / 100	241 ms	115796 KiB

dna

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> p;
vector<map<char, map<char, int>>> l;
vector<map<char, int>> s, t;

void init(string a, string b) {
    n = int(a.size());
    p.assign(n, 0);
    l.assign(n, {});
    s.assign(n, {});
    t.assign(n, {});
    for (int i = 0; i < n; ++i) {
        p[i] = a[i] != b[i];
        if (i) p[i] += p[i - 1], l[i] = l[i - 1], s[i] = s[i - 1], t[i] = t[i - 1];
        l[i][a[i]][b[i]]++;
        s[i][a[i]]++;
        t[i][b[i]]++;
    }
}

int get_distance(int x, int y) {
    if (s[y]['A'] - (x ? s[x - 1]['A'] : 0) != t[y]['A'] - (x ? t[x - 1]['A'] : 0) || s[y]['C'] - (x ? s[x - 1]['C'] : 0) != t[y]['C'] - (x ? t[x - 1]['C'] : 0) || s[y]['T'] - (x ? s[x - 1]['T'] : 0) != t[y]['T'] - (x ? t[x - 1]['T'] : 0)) return -1;
    auto u = l[y];
    if (x) for (auto &[q, w] : l[x - 1]) for (auto &[e, r] : w) u[q][e] -= r;
    int ans = 0, m = y - x + 1 - u['A']['A'] - u['C']['C'] - u['T']['T'], k = min(u['A']['C'], u['C']['A']);
    ans += k;
    m -= k * 2;
    k = min(u['A']['T'], u['T']['A']);
    ans += k;
    m -= k * 2;
    k = min(u['C']['T'], u['T']['C']);
    ans += k;
    m -= k * 2;
    ans += m / 3 * 2;
    return ans;
}

//int main() {
//    init("ATACAT", "ACTATA");
//    cout << get_distance(1, 3) << '\n';
//    cout << get_distance(4, 5) << '\n';
//    cout << get_distance(3, 5) << '\n';
//    return 0;
//}

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