Submission #1179082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179082		pandaa73	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	3095 ms	27824 KiB

Main

#include <bits/stdc++.h>
#include <random>
using namespace std;

#define lf "\n"
#define ff endl
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

#define infos(str) do { fprintf(stderr, str"\n"); } while(0)
#define infor(str, ...) do { fprintf(stderr, str, __VA_ARGS__); } while(0)
#define infof(str, ...) do { fprintf(stderr, str"\n", __VA_ARGS__); } while(0)

#ifndef DEBUG

#undef infos
#undef infor
#undef infof

#define infos(str)
#define infor(str, ...)
#define infof(str, ...)

#endif

using ll = long long;

constexpr int LOG = 20;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
using Treap = struct Node *;

struct Node {
    int pri;

    int val;
    int sz;

    int id;

    Treap l;
    Treap r;

    Node(int val): pri(mt()), val(val), sz(1) {
        static int id = 0;

        infof("- Created new node %d with %d", id, val);

        this->id = id++;

        l = r = NULL;
    }

    void operator~(void) {
        delete l;
        delete r;
    }
};

int sz(Treap v) {
    return v ? v->sz : 0;
}

void pull(Treap v) {
    if(!v) return;

    v->sz = sz(v->l) + 1 + sz(v->r);
}

int first(Treap v) {
    if(v->l) return first(v->l);

    return v->val;
}

Treap merge(Treap l, Treap r) {
    if(!l || !r) return l ? l : r;

    //infof("... Merging %d with %d", l->id, r->id);

    if(l->pri > r->pri) {
        l->r = merge(l->r, r);
        pull(l);

        if(l->r) assert(l->r->id != l->id);

        return l;
    }

    r->l = merge(l, r->l);
    pull(r);

    if(r->l) assert(r->l->id != r->id);

    return r;
}

array<Treap, 2> split(Treap v, int i) {
    if(!v) return {NULL, NULL};

    //infof("... Splitting %d | sz_l: %d, sz_r: %d", v->id, sz(v->l), sz(v->r));

    if(sz(v->l) >= i) {
        if(v->l) assert(v->l->id != v->id);

        auto [l, r] = split(v->l, i);

        v->l = r;
        pull(v);

        return {l, v};
    } else {
        if(v->r) assert(v->r->id != v->id);

        auto [l, r] = split(v->r, i - sz(v->l) - 1);

        v->r = l;
        pull(v);

        return {v, r}; 
    }
}

Treap find(Treap v, int i) {
    if(!v) return 0;

    //infof("... Finding %d [%d, %d]", i, sz(v->l), sz(v->r));

    if(sz(v->l) == i)
        return v;

    if(sz(v->l) > i && v->l)
        assert(v->l->id != v->id);
    if(sz(v->r) > i && v->r)
        assert(v->r->id != v->id);

    if(sz(v->l) > i)
        return find(v->l, i);
    else return find(v->r, i - sz(v->l) - 1);
}

void print(Treap v) {
    if(!v) return;

    print(v->l);

    infor("%d [%d] ", v->val, v->id);

    print(v->r);
}

Treap shuffler(Treap v, int k) {
    pull(v);

    const int N = sz(v);

    auto [l, r] = split(v, N / 2);

    infof("K = %d: split into sizes: sz_l %d, sz_r %d", k, sz(l), sz(r));

    assert(sz(l) == sz(r));

    v = NULL;

    Treap block_l = NULL, block_r = NULL;
    for(; sz(l) && sz(r);) {
        if(!block_l) {
            infor("- Splitting L | sz is %d | ", sz(l));

            auto ret = split(l, k);
            block_l = ret[0], l = ret[1];
            
            infof("block: %d ; rest: %d", sz(block_l), sz(l));
        }

        if(!block_r) {
            infor("- Splitting R | sz is %d | ", sz(r));

            auto ret = split(r, k);
            block_r = ret[0], r = ret[1];

            infof("block: %d ; rest: %d", sz(block_r), sz(r));
        }

        infof("- First L: %d | First R: %d", first(block_l), first(block_r));

        if(first(block_l) < first(block_r))
            v = merge(v, block_l), block_l = NULL;
        else v = merge(v, block_r), block_r = NULL;
    }

    l = merge(block_l, l);
    r = merge(block_r, r);

    if(sz(l)) v = merge(v, l);
    if(sz(r)) v = merge(v, r);

    return v;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N, Q; cin >> N >> Q;

    vector<int> V(N);
    for(auto &x: V) cin >> x;

    vector<array<int, 2>> Qs(Q);
    for(auto &[t, i]: Qs) cin >> t >> i, i--;

    vector<int> order(Q); iota(all(order), 0);
    sort(all(order), [&](int i, int j) -> bool {
        return Qs[i] < Qs[j];
    });

    vector<int> ans(Q);

    vector<Treap> nodes(N);
    Treap v = new Node(V[0]);

    nodes[0] = v;
    for(int i = 1; i < N; ++i)
        v = merge(v, nodes[i] = new Node(V[i]));

    infof("Initialized treap with %d nodes", sz(v));

    infos("Treap at start:");
    print(v); infos("");

    int it = 0;

    int curr = 0;
    for(int q: order) {
        infos("================");
        infof("%d: size of treap is %d", it++, sz(v));

        auto [t, idx] = Qs[q];

        infof("Solving %d %d", t, idx);
        infos("");

        if(t > N) {
            ans[q] = V[idx];  

            continue;
        }

        for(; curr < t; ++curr) {
            v = shuffler(v, 1);

            infos("");
            infof("Treap at %d:", curr + 1);
            print(v); infos("");
            infos("");
        }

        infof("searching index %d in treap of size %d", idx, sz(v));
        Treap node = find(v, idx);
        assert(node);

        ans[q] = node->val;
        infof("ANSWER FOR %d: %d", q, ans[q]);
    }

    for(auto x: ans)
        cout << x << lf;

    cout.flush();

    infof("treap has %d nodes", sz(v));
    print(v); infos("");

    for(auto x: nodes) delete x;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25