Submission #1214882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214882		thangdz2k7	Mechanical Doll (IOI18_doll)	C++20	0 / 100	0 ms	324 KiB

doll

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

using namespace std;

void create_circuit(int M, vector <int> A){
    vector <int> C(M + 1, -1);
    vector <int> X, Y;
    int nNode = 0;

    A.push_back(0);
    int N = A.size();
    int b = 1;
    while (b < N) b *= 2;

    function <int(int, int)> dfs = [&](int l, int r){
        if (l >= N) return -1;
        if (l < r){
            int mid = l + r >> 1;
            nNode ++; int cur = nNode;
            X.push_back(dfs(l, mid));
            Y.push_back(dfs(mid + 1, r));
            return -cur;
        }
        return 1;
    };

    dfs(0, b - 1);
    vector <int> vis(nNode, 0);
    for (int i : A){
        int u = 0;
        while (u > -1){
            vis[u] ^= 1;
            int &to = vis[u] ? X[u] : Y[u];
            if (to > 0) to = i, u = -1;
            else u = -(to + 1);
        }
    }

    answer(C, X, Y);
}

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