IOI 2021 day 2

dna.cpp

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<vector<int>>> cnt;

map<char, int> id;

void init(string a, string b) {
    n = a.size();
    id['A'] = 0;
    id['T'] = 1;
    id['C'] = 2;
    a = ' ' + a;
    b = ' ' + b;

    cnt.resize(3, vector<vector<int>>(3, vector<int>(n + 1)));
    for(int i = 1; i <= n; i++){
        cnt[id[a[i]]][id[b[i]]][i]++;
        for(int t1 = 0; t1 < 3; t1++){
            for(int t2 = 0; t2 < 3; t2++) cnt[t1][t2][i] += cnt[t1][t2][i - 1];
        }
    }
}

int get_distance(int x, int y) {
    x++; y++;
    
    vector<vector<int>> now(3, vector<int>(3));
    vector<int> c1(3), c2(3);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            now[i][j] = cnt[i][j][y] - cnt[i][j][x - 1];
            c1[i] += now[i][j];
            c2[j] += now[i][j];
        }
    }

    for(int i = 0; i < 3; i++){
        if(c1[i] != c2[i]) return -1;
    }

    int ans = 0;
    for(int i = 0; i < 3; i++){
        for(int j = i + 1; j < 3; j++){
            int tmp = min(now[i][j], now[j][i]);
            now[i][j] -= tmp;
            now[j][i] -= tmp;
            ans += tmp;
        }
    }

    int tv = -1;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if(i == j || now[i][j] == 0) continue;
            if(tv == -1) tv = now[i][j];
            assert(tv == now[i][j]);
        }
    }
    if(tv == -1) return ans;
    ans += tv * 2;
	return ans;
}

dungeons.cpp

#include "dungeons.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> w, s;
vector<vector<int>> go;
vector<ll> ss;
vector<vector<ll>> ps, mx;
int SZ = 30;
int n;

void init(int _n, vector<int> _s, vector<int> p, vector<int> _w, vector<int> l) {
    n = _n;
    s = _s;
    w = _w;
    ss.resize(n + 1);
    ps.resize(n + 1, vector<ll>(SZ));
    go.resize(n + 1, vector<int>(SZ));
    mx.resize(n + 1, vector<ll>(SZ));
    
    for(int i = n - 1; i >= 0; i--){
        ss[i] = s[i];
        if(w[i] != n) ss[i] += ss[w[i]];
        go[i][0] = l[i];
        ps[i][0] = p[i];
        mx[i][0] = s[i] - 1;
    }
    go[n][0] = n;

    for(int i = 1; i < SZ; i++){
        for(int j = 0; j <= n; j++){
            go[j][i] = go[go[j][i - 1]][i - 1];
            ps[j][i] = ps[j][i - 1] + ps[go[j][i - 1]][i - 1];
            mx[j][i] = min(mx[j][i - 1], mx[go[j][i - 1]][i - 1] - ps[j][i - 1]);
        }
    }
}

ll simulate(int now, int _z){
    ll z = _z;

    while(now < n && z < 10000000){
        for(int i = SZ - 1; i >= 0; i--){
            if(z > mx[now][i]) continue;
            z += ps[now][i];
            now = go[now][i];
        }
        assert(z >= s[now]);
        z += s[now];
        now = w[now];
    }
    z += ss[now];

	return z;
}

dungeons1.cpp

#include "dungeons.h"

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

typedef long long ll;

vector<int> w, s;
vector<vector<int>> go;
vector<ll> ss;
vector<vector<ll>> ps, mx;
ll mxs = 0;
int SZ = 30;
int n;

void init(int _n, vector<int> _s, vector<int> p, vector<int> _w, vector<int> l) {
    n = _n;
    s = _s;
    w = _w;
    ss.resize(n + 1);
    ps.resize(n + 1, vector<ll>(SZ));
    go.resize(n + 1, vector<int>(SZ));
    mx.resize(n + 1, vector<ll>(SZ));
    w.eb(n);
    s.eb();
    
    for(int i = n - 1; i >= 0; i--){
        mxs = max(mxs, (ll)s[i]);
        ss[i] = s[i];
        if(w[i] != n) ss[i] += ss[w[i]];
        go[i][0] = l[i];
        ps[i][0] = p[i];
        mx[i][0] = s[i] - 1;
    }
    go[n][0] = n;

    for(int i = 1; i < SZ; i++){
        for(int j = 0; j <= n; j++){
            go[j][i] = go[go[j][i - 1]][i - 1];
            ps[j][i] = ps[j][i - 1] + ps[go[j][i - 1]][i - 1];
            mx[j][i] = min(mx[j][i - 1], mx[go[j][i - 1]][i - 1] - ps[j][i - 1]);
        }
    }
}

ll simulate(int now, int _z){
    ll z = _z;

    while(now < n && z < mxs){
        for(int i = SZ - 1; i >= 0; i--){
            if(z > mx[now][i]) continue;
            z += ps[now][i];
            now = go[now][i];
        }
        z += s[now];
        now = w[now];
    }
    z += ss[now];

	return z;
}

dungeons2.cpp

#include "dungeons.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())

using namespace std;

typedef long long ll;

vector<int> w, s;
vector<vector<vector<int>>> go;
vector<ll> ss;
vector<vector<vector<ll>>> ps, mx;
vector<int> discr;
ll mxs = 0;
int SZ = 30;
int sz;
int n;
const ll MAX = 1LL << 60;

int gd(int v){
    return lower_bound(iter(discr), v) - discr.begin();
}

void init(int _n, vector<int> _s, vector<int> p, vector<int> _w, vector<int> l) {
    n = _n;
    s = _s;
    w = _w;
    w.eb(n);
    l.eb(n);
    s.eb();
    p.eb();
    discr = s;
    lsort(discr);
    uni(discr);
    sz = discr.size();

    ss.resize(n + 1);
    ps.resize(sz, vector<vector<ll>>(n + 1, vector<ll>(SZ)));
    go.resize(sz, vector<vector<int>>(n + 1, vector<int>(SZ)));
    mx.resize(sz, vector<vector<ll>>(n + 1, vector<ll>(SZ)));
    
    for(int i = n; i >= 0; i--){
        mxs = max(mxs, (ll)s[i]);
        ss[i] = s[i];
        if(w[i] != n) ss[i] += ss[w[i]];
        int id = gd(s[i]);
        for(int j = 0; j < sz; j++){
            if(j >= id){
                go[j][i][0] = w[i];
                ps[j][i][0] = s[i];
                mx[j][i][0] = MAX;
                continue;
            }
            go[j][i][0] = l[i];
            ps[j][i][0] = p[i];
            mx[j][i][0] = s[i] - 1;
        }
    }

    for(int k = 0; k < sz; k++){
        for(int i = 1; i < SZ; i++){
            for(int j = 0; j <= n; j++){
                go[k][j][i] = go[k][go[k][j][i - 1]][i - 1];
                ps[k][j][i] = ps[k][j][i - 1] + ps[k][go[k][j][i - 1]][i - 1];
                mx[k][j][i] = min(mx[k][j][i - 1], mx[k][go[k][j][i - 1]][i - 1] - ps[k][j][i - 1]);
            }
        }
    }
}

ll simulate(int now, int _z){
    ll z = _z;

    while(now < n && z < mxs){
        int k = upper_bound(iter(discr), z) - discr.begin();
        k--;
        for(int i = SZ - 1; i >= 0; i--){
            if(z > mx[k][now][i]) continue;
            z += ps[k][now][i];
            now = go[k][now][i];
        }
        z += s[now];
        now = w[now];
    }
    z += ss[now];

	return z;
}

dungeons3.cpp

#include "dungeons.h"

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

typedef long long ll;

vector<int> w, s, l, p;
vector<vector<int>> gol, gow;
vector<vector<ll>> ss, mn;
vector<vector<ll>> ps, mx;
int SZ = 30;
int n;

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n;
    s = _s;
    w = _w;
    p = _p;
    l = _l;
    s.eb();
    p.eb();
    w.eb(n);
    l.eb(n);
    ps.resize(n + 1, vector<ll>(SZ));
    gol.resize(n + 1, vector<int>(SZ));
    mx.resize(n + 1, vector<ll>(SZ));
    ss.resize(n + 1, vector<ll>(SZ));
    gow.resize(n + 1, vector<int>(SZ));
    mn.resize(n + 1, vector<ll>(SZ));
    
    for(int i = 0; i <= n; i++){
        ps[i][0] = p[i];
        ss[i][0] = s[i];
        gol[i][0] = l[i];
        gow[i][0] = w[i];
        mx[i][0] = s[i] - 1;
        mn[i][0] = s[i];
    }

    for(int i = 1; i < SZ; i++){
        for(int j = 0; j <= n; j++){
            gol[j][i] = gol[gol[j][i - 1]][i - 1];
            ps[j][i] = ps[j][i - 1] + ps[gol[j][i - 1]][i - 1];
            mx[j][i] = min(mx[j][i - 1], mx[gol[j][i - 1]][i - 1] - ps[j][i - 1]);

            gow[j][i] = gow[gow[j][i - 1]][i - 1];
            ss[j][i] = ss[j][i - 1] + ss[gow[j][i - 1]][i - 1];
            mn[j][i] = max(mn[j][i - 1], mn[gow[j][i - 1]][i - 1] - ss[j][i - 1]);
        }
    }
}

ll simulate(int now, int _z){
    ll z = _z;

    while(now < n){
        if(z < s[now]){
            for(int i = SZ - 1; i >= 0; i--){
                if(z > mx[now][i]) continue;
                z += ps[now][i];
                now = gol[now][i];
            }
        }
        else{
            for(int i = SZ - 1; i >= 0; i--){
                if(z < mn[now][i]) continue;
                z += ss[now][i];
                now = gow[now][i];
            }
        }
    }

	return z;
}

registers.cpp

#include "registers.h"

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

typedef long long ll;

int n, k;

void getmin(){
    append_xor(3, 1, 2);

    append_move(4, 3);
    for(int i = 0; (1 << i) < k; i++){
        append_right(5, 4, 1 << i);
        append_or(4, 4, 5);
    }

    append_not(5, 4);
    append_right(5, 5, 1);
    append_and(4, 4, 5);
    // high bit of 3 at 4
    append_print(3);
    append_print(4);
    
    append_and(5, 1, 4);
    for(int i = 0; (1 << i) < k; i++){
        append_right(6, 5, 1 << i);
        append_or(5, 5, 6);
    }
    append_and(5, 3, 5);
    append_xor(1, 1, 5);

    append_and(5, 2, 4);
    for(int i = 0; (1 << i) < k; i++){
        append_right(6, 5, 1 << i);
        append_or(5, 5, 6);
    }
    append_and(5, 3, 5);
    append_xor(2, 2, 5);
}

void construct_instructions(int s, int _n, int _k, int q) {
    n = _n;
    k = _k;

    vector<bool> msk(2000);
    for(int i = 0; i < k; i++) msk[i] = true;
    append_store(99, msk);
    
    append_move(1, 0);
    append_and(1, 1, 99);
    for(int i = 1; i < n; i++){
        append_right(2, 0, k * i);
        append_and(2, 2, 99);
        getmin();
    }
    append_move(0, 1);
}

registers1.cpp

#include "registers.h"

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

typedef long long ll;

int n, k;

void getmin(){
    append_xor(3, 0, 1);

    append_move(4, 3);
    for(int i = 0; (1 << i) < k; i++){
        append_right(5, 4, 1 << i);
        append_or(4, 4, 5);
    }

    append_not(5, 4);
    append_right(5, 5, 1);
    append_and(4, 4, 5);
    // high bit of 3 at 4
    append_print(3);
    append_print(4);
    
    append_and(5, 0, 4);
    for(int i = 0; (1 << i) < k; i++){
        append_right(6, 5, 1 << i);
        append_or(5, 5, 6);
    }
    append_and(5, 3, 5);
    append_xor(0, 0, 5);

    append_and(5, 1, 4);
    for(int i = 0; (1 << i) < k; i++){
        append_right(6, 5, 1 << i);
        append_or(5, 5, 6);
    }
    append_and(5, 3, 5);
    append_xor(1, 1, 5);
}

void construct_instructions(int s, int _n, int _k, int q) {
    n = _n;
    k = _k;

    vector<bool> msk(2000);
    for(int i = 0; i < k; i++) msk[i] = true;
    append_store(99, msk);
    
    append_right(1, 0, k);
    append_and(0, 0, 99);

    getmin();
}

registers2.cpp

#include "registers.h"

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

typedef long long ll;

int n, k;

void getmin(int a, int b){
    append_print(a);
    append_print(b);
    append_xor(11, a, b);

    append_move(12, 11);
    for(int i = 0; (1 << i) < k; i++){
        append_right(13, 12, 1 << i);
        append_or(12, 12, 13);
    }

    append_not(13, 12);
    append_right(13, 13, 1);
    append_and(12, 12, 13);
    // high bit of 11 at 12
    append_print(11);
    append_print(12);
    
    append_and(13, a, 12);
    for(int i = 0; (1 << i) < k; i++){
        append_right(14, 13, 1 << i);
        append_or(13, 13, 14);
    }
    append_and(13, 11, 13);
    append_xor(a, a, 13);

    append_xor(b, a, 11);
    append_print(a);
    append_print(b);
}

void construct_instructions(int s, int _n, int _k, int q) {
    n = _n;
    k = _k;
    assert(n <= 10 && s == 1);

    vector<bool> msk(2000);
    for(int i = 0; i < k; i++) msk[i] = true;
    append_store(99, msk);

    for(int i = 1; i <= n; i++){
        append_right(i, 0, k * (i - 1));
        append_and(i, i, 99);
    }
    
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - i - 1; j++){
            getmin(j + 1, j + 2);
        }
    }
    append_move(0, 1);
    for(int i = 2; i <= n; i++){
        append_left(i, i, k * (i - 1));
        append_or(0, 0, i);
    }

}