Submission #1265878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265878		BlockOG	Mutating DNA (IOI21_dna)	C++20	43 / 100	1596 ms	5132 KiB

dna

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

struct Node {
    int ne = 0;
    int aa = 0, at = 0, ac = 0;
    int ba = 0, bt = 0, bc = 0;

    Node operator+(const Node &other) const {
        Node res;
        res.ne = ne + other.ne;
        res.aa = aa + other.aa;
        res.at = at + other.at;
        res.ac = ac + other.ac;
        res.ba = ba + other.ba;
        res.bt = bt + other.bt;
        res.bc = bc + other.bc;
        return res;
    }

    Node operator-(const Node &other) const {
        Node res;
        res.ne = ne - other.ne;
        res.aa = aa - other.aa;
        res.at = at - other.at;
        res.ac = ac - other.ac;
        res.ba = ba - other.ba;
        res.bt = bt - other.bt;
        res.bc = bc - other.bc;
        return res;
    }

    bool valid() const {
        return aa == ba && at == bt && ac == bc;
    }
};

Node bit[100001];

Node get(int i) {
    Node res;
    for (i++; i > 0; i -= i & -i) res = res + bit[i];
    return res;
}

void add(int i, Node v) {
    for (i++; i <= 100000; i += i & -i) bit[i] = bit[i] + v;
}

string _a, _b;

void init(string a, string b) {
    _a = a, _b = b;

    fo(i, 0, a.size()) {
        Node res;
        res.ne = a[i] != b[i];

        res.aa = a[i] == 'A';
        res.at = a[i] == 'T';
        res.ac = a[i] == 'C';

        res.ba = b[i] == 'A';
        res.bt = b[i] == 'T';
        res.bc = b[i] == 'C';

        add(i, res);
    }
}

int get_distance(int x, int y) {
    string a(_a), b(_b);
    int swaps = 0;
    fo(i, x, y + 1) {
        if (a[i] == b[i]) continue;

        fo(j, i + 1, y + 1) {
            if (a[j] != b[j] && a[j] == b[i]) {
                swap(a[i], a[j]);
                swaps++;
                goto cont;
            }
        }

        return -1;
    cont:;
    }

    return swaps;

    Node res = get(y) - get(x - 1);
    return res.valid() ? max(res.ne - 1, 0) : -1;
}

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