Submission #995469

#	Time	Username	Problem	Language	Result	Execution time	Memory
995469		Forested	Mechanical Doll (IOI18_doll)	C++17	100 / 100	368 ms	11976 KiB

doll

#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include "doll.h"

i32 floor_log2(i32 n) {
    i32 k = 0;
    while ((1 << (k + 1)) <= n) {
        ++k;
    }
    return k;
}

i32 ceil_log2(i32 n) {
    i32 k = 0;
    while ((1 << k) < n) {
        ++k;
    }
    return k;
}

i32 bitrev(i32 n, i32 x) {
    i32 y = 0;
    REP(i, n) {
        if (x & (1 << i)) {
            y ^= 1 << (n - 1 - i);
        }
    }
    return y;
}

void create_circuit(i32 m, V<i32> a) {
    i32 n = LEN(a);
    i32 l = ceil_log2(n + 1);
    V<i32> use(1 << l, 0);
    REP(i, n + 1) {
        i32 p = (1 << l) - 1 - i / 2;
        while (p > 0) {
            use[p] = 1;
            p /= 2;
        }
    }
    V<i32> idx(1 << l, -1);
    i32 s = 0;
    REP(i, 1 << l) {
        if (use[i]) {
            idx[i] = s++;
        }
    }
    V<i32> c(m + 1, -1);
    V<i32> x(s, -1), y(s, -1);
    REP(i, 1, 1 << (l - 1)) {
        if (!use[i]) {
            continue;
        }
        if (use[2 * i]) {
            x[idx[i]] = -(idx[2 * i] + 1);
        }
        if (use[2 * i + 1]) {
            y[idx[i]] = -(idx[2 * i + 1] + 1);
        }
    }
    V<i32> vals;
    REP(i, n + 1) {
        vals.push_back((1 << l) - 1 - i);
    }
    sort(ALL(vals), [&](i32 x, i32 y) -> bool {
        return bitrev(l, x) < bitrev(l, y);
    });
    REP(i, n + 1) {
        i32 v = vals[i];
        i32 node = (1 << (l - 1)) + v / 2;
        bool is_left = v % 2 == 0;
        i32 to = i == n ? 0 : a[i];
        if (is_left) {
            x[idx[node]] = to;
        } else {
            y[idx[node]] = to;
        }
    }
    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