Submission #1024286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024286		efishel	Mechanical Doll (IOI18_doll)	C++17	100 / 100	117 ms	39476 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

struct Switch {
    Switch *x, *y;
    bool pointX;
    ll id;
    ll in, act;
    bool isEnd;
    bool isAct;

    Switch (ll in, ll act): x(0), y(0), pointX(true), in(in), act(act), isEnd(false) {
        if (act == 0) { isEnd = true; isAct = false; return; }
        if (act == 1 && in == 1) { isEnd = true; isAct = true; return; }
        ll goR = min(in/2, act);
        x = new Switch(in/2, act-goR);
        y = new Switch(in/2, goR);
    }

    ll dfs (ll &timer, vll &toX, vll &toY) {
        if (isEnd) return 15;
        id = timer--;
        toX[-id-1] = x->dfs(timer, toX, toY);
        toY[-id-1] = y->dfs(timer, toX, toY);
        return id;
    }

    pair <ll, ll> trig (ll par, ll st) {
        if (isEnd) return isAct ? pair <ll, ll>{ par, st } : pair <ll, ll>{ par, st+2 };
        if (pointX ^= 1)
            return y->trig(id, 0);
        else
            return x->trig(id, 1);
    }
};

void create_circuit (int m, vi A) {
    vll ve(A.begin(), A.end());
    ve.push_back(0);
    ll n = ve.size();
    if (n == 2) { // bruh edge case
        vi to(m+1, 0);
        to[0] = ve[0];
        answer(to, {}, {});
        return;
    }
    ll pow2 = 2<<__lg(n-1);
    ll timer = -1;
    Switch root(pow2, n);
    vll toX(pow2, 15), toY(pow2, 15);
    ll rootId = root.dfs(timer, toX, toY);
    ll c = 0;
    for (ll i = 0; i < pow2; i++) {
        auto [a, st] = root.trig(17, false);
        a = -a-1;
        if (st >= 2) {
            (st-2 ? toX : toY)[a] = rootId;
            continue;
        }
        (st ? toX : toY)[a] = ve[c];
        c++;
    }
    ll sz = -min(*min_element(toX.begin(), toX.end()), *min_element(toY.begin(), toY.end()));
    toX.resize(sz);
    toY.resize(sz);
    answer(vi(m+1, -1), vi(toX.begin(), toX.end()), vi(toY.begin(), toY.end()));
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56