Submission #1265889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265889		BlockOG	Mutating DNA (IOI21_dna)	C++20	100 / 100	35 ms	7432 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 nat = 0, nac = 0;
    int nta = 0, ntc = 0;
    int nca = 0, nct = 0;

    int aa = 0, at = 0, ac = 0;
    int ba = 0, bt = 0, bc = 0;

    Node operator+(const Node &other) const {
        Node res;

        res.nat = nat + other.nat;
        res.nac = nac + other.nac;
        res.nta = nta + other.nta;
        res.ntc = ntc + other.ntc;
        res.nca = nca + other.nca;
        res.nct = nct + other.nct;

        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.nat = nat - other.nat;
        res.nac = nac - other.nac;
        res.nta = nta - other.nta;
        res.ntc = ntc - other.ntc;
        res.nca = nca - other.nca;
        res.nct = nct - other.nct;

        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;
    }

    int swaps() const {
        if (!valid()) return -1;

        Node res = *this;

        int sac = min(res.nac, res.nca);
        int stc = min(res.ntc, res.nct);

        return res.nca + res.nct + min(res.nta + res.nca - sac, res.nat + res.nct - stc);
    }
};

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;
}

void init(string a, string b) {
    fo(i, 0, a.size()) {
        Node res;

        res.nat = a[i] == 'A' && b[i] == 'T';
        res.nac = a[i] == 'A' && b[i] == 'C';
        res.nta = a[i] == 'T' && b[i] == 'A';
        res.ntc = a[i] == 'T' && b[i] == 'C';
        res.nca = a[i] == 'C' && b[i] == 'A';
        res.nct = a[i] == 'C' && b[i] == 'T';

        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) {
    return (get(y) - get(x - 1)).swaps();
}

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