Submission #1214893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214893		thangdz2k7	Mechanical Doll (IOI18_doll)	C++20	100 / 100	84 ms	10036 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);
    int nNode = 0;

    A.push_back(0);
    int N = A.size();
    vector <int> X(N * 2), Y(N * 2);
    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 - 1){
            int mid = l + r >> 1;
            nNode ++; int cur = nNode;
            Y[cur - 1] = dfs(l, mid);
            X[cur - 1] = dfs(mid, r);
            return -cur;
        }
        return 1;
    };

    dfs(0, b);
    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);
        }
    }

    X.resize(nNode); Y.resize(nNode);
    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