Submission #995505

#	Time	Username	Problem	Language	Result	Execution time	Memory
995505		shiomusubi496	Mechanical Doll (IOI18_doll)	C++17	100 / 100	97 ms	8864 KiB

doll

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

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    vector<int> C(M + 1, -1);
    int lev = 0;
    while ((1 << (lev + 1)) <= N) ++lev;
    vector<int> X, Y;
    while (lev >= 0) {
        int n = 1 << lev;
        if (n > N) {
            X.push_back(-1);
            Y.push_back(0);
            --lev;
            if (lev >= 0) Y.back() = -(int)X.size() - 1;
            continue;
        }
        N -= n;
        if (n == 1) {
            X.push_back(1);
            Y.push_back(0);
            --lev;
        }
        else {
            X.push_back(-(int)X.size() - 2);
            Y.push_back(0);
            int idx = Y.size() - 1;
            int tmp = X.size();
            rep2 (i, 1, n / 2) {
                X.push_back(-(tmp + i * 2));
                Y.push_back(-(tmp + i * 2 + 1));
            }
            rep2 (i, n / 2, n) {
                X.push_back(1);
                Y.push_back(1);
            }
            --lev;
            Y[idx] = -(int)X.size() - 1;
        }
    }
    {
        int cur = 0;
        int idx = 0;
        vector<bool> sw(X.size(), true);
        do {
            if (cur >= 0) cur = C[cur];
            else {
                if (sw[-1 - cur]) {
                    sw[-1 - cur] = false;
                    if (X[-1 - cur] > 0) X[-1 - cur] = A[idx++];
                    cur = X[-1 - cur];
                }
                else {
                    sw[-1 - cur] = true;
                    if (Y[-1 - cur] > 0) Y[-1 - cur] = A[idx++];
                    cur = Y[-1 - cur];
                }
            }
        } while (cur != 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