oj.uz

Submission #995469

# Submission time Handle Problem Language Result Execution time Memory
995469 2024-06-09T06:50:19 Z Forested Mechanical Doll (IOI18_doll) C++17
100 / 100
 368 ms 11976 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 110 ms 5276 KB Output is correct
3 Correct 119 ms 4772 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 159 ms 6860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 110 ms 5276 KB Output is correct
3 Correct 119 ms 4772 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 159 ms 6860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 234 ms 8688 KB Output is correct
9 Correct 259 ms 9100 KB Output is correct
10 Correct 339 ms 11976 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 110 ms 5276 KB Output is correct
3 Correct 119 ms 4772 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 159 ms 6860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 234 ms 8688 KB Output is correct
9 Correct 259 ms 9100 KB Output is correct
10 Correct 339 ms 11976 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 327 ms 11720 KB Output is correct
15 Correct 215 ms 8388 KB Output is correct
16 Correct 335 ms 11460 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 321 ms 11904 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 432 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 234 ms 7940 KB Output is correct
3 Correct 253 ms 7876 KB Output is correct
4 Correct 336 ms 10988 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 234 ms 7940 KB Output is correct
3 Correct 253 ms 7876 KB Output is correct
4 Correct 336 ms 10988 KB Output is correct
5 Correct 338 ms 11460 KB Output is correct
6 Correct 319 ms 11156 KB Output is correct
7 Correct 368 ms 11184 KB Output is correct
8 Correct 308 ms 10948 KB Output is correct
9 Correct 236 ms 7968 KB Output is correct
10 Correct 327 ms 10952 KB Output is correct
11 Correct 326 ms 10948 KB Output is correct
12 Correct 250 ms 7880 KB Output is correct
13 Correct 227 ms 7996 KB Output is correct
14 Correct 253 ms 8260 KB Output is correct
15 Correct 252 ms 8280 KB Output is correct
16 Correct 6 ms 856 KB Output is correct
17 Correct 301 ms 7072 KB Output is correct
18 Correct 226 ms 7880 KB Output is correct
19 Correct 253 ms 7920 KB Output is correct
20 Correct 318 ms 10952 KB Output is correct
21 Correct 336 ms 10904 KB Output is correct
22 Correct 327 ms 10952 KB Output is correct