Submission #837746

#	Time	Username	Problem	Language	Result	Execution time	Memory
837746		becaido	Mechanical Doll (IOI18_doll)	C++17	100 / 100	90 ms	8736 KiB

doll

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

void create_circuit(int M, vector<int> A) {
    int N, cur = 0;
    vector<int> C(M + 1, -1), X, Y;
    A.emplace_back(0), N = A.size();
    auto rec = [&](auto rec, int sz, int dep)->int {
        cur++;
        int pos = -cur, i = -(pos + 1);
        X.emplace_back(-1), Y.emplace_back(-1);
        if (dep == 0) {
            if (sz == 1) Y[i] = 0;
            if (sz == 2) X[i] = Y[i] = 0;
            return pos;
        }
        int half = 1 << dep;
        if (sz <= half) Y[i] = rec(rec, sz, dep - 1);
        else {
            X[i] = rec(rec, sz - half, dep - 1);
            Y[i] = rec(rec, half, dep - 1);
        }
        return pos;
    };
    rec(rec, N, __lg(N - 1));
    vector<int> b(cur, 0);
    int p = 0, pos = -1;
    while (p < N) {
        int i = -(pos + 1);
        if (b[i] == 0) {
            if (X[i] == 0) X[i] = A[p++], pos = -1;
            else pos = X[i];
        } else {
            if (Y[i] == 0) Y[i] = A[p++], pos = -1;
            else pos = Y[i];
        }
        b[i] ^= 1;
    }
    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