Submission #604972

#	Time	Username	Problem	Language	Result	Execution time	Memory
604972		piOOE	Mechanical Doll (IOI18_doll)	C++17	100 / 100	141 ms	8716 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

void create_circuit(int m, vector<int> a) {
    int n = (int) a.size();
    vector<int> c(m + 1, 0), x, y;
    c[0] = a[0];
    a.push_back(0);
    a.erase(a.begin());

    auto create = [&]() {
        x.push_back(0), y.push_back(0);
        return (int) x.size();
    };

    int root = create();

    fill(c.begin() + 1, c.end(), -root);

    constexpr int inf = 228228228;

    function<void(int, int, int)> solve = [&](int v, int sz, int real) -> void {
        assert(real > 0);
        assert(sz > 1);
        if (sz == 2) {
            y[v - 1] = inf;
            real -= 1;
        } else {
            int R = min(sz >> 1, real);
            int nxt = create();
            y[v - 1] = -nxt;
            solve(nxt, sz >> 1, R);
            real -= R;
        }
        if (real <= 0) {
            x[v - 1] = -root;
        } else {
            if (sz == 2) {
                x[v - 1] = inf;
            } else {
                int nxt = create();
                x[v - 1] = -nxt;
                solve(nxt, sz >> 1, real);
            }
        }
    };

    int sz = 2;
    while (sz < n) sz <<= 1;

    solve(root, sz, n);

    int cur = c[0], pnt = 0;

    vector<int> tp((int) x.size());

    while (cur != 0) {
        if (cur > 0) {
            cur = c[cur];
            continue;
        } else {
            cur = -cur;
            if (tp[cur - 1] == 0) {
                if (x[cur - 1] == inf) {
                    assert(pnt < n);
                    x[cur - 1] = a[pnt++];
                }
                tp[cur - 1] ^= 1;
                cur = x[cur - 1];
            } else {
                if (y[cur - 1] == inf) {
                    assert(pnt < n);
                    y[cur - 1] = a[pnt++];
                }
                tp[cur - 1] ^= 1;
                cur = y[cur - 1];
            }
        }
    }

    assert(all_of(tp.begin(), tp.end(), [](int i) {
        return i == 0;
    }));

    answer(c, x, y);
}

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