oj.uz

Submission #713640

# Submission time Handle Problem Language Result Execution time Memory
713640 2023-03-22T17:52:42 Z jophyyjh Mechanical Doll (IOI18_doll) C++14
100 / 100
 72 ms 12892 KB 
/**
 * An interesting construction~
 * [Tree] It was quite straight-forward (for me) to come up with a tree solution.
 *      Namely, each trigger's exit should point to a single switch known as the
 *      "root" of our tree. Our switches form shall form a rooted binary tree, with
 *      the exits of the leaves pointing back to the triggers, as specified in the
 *      input order. This idea is best illustrated when N is a power of 2 ([S4]). In
 *      this case, we assign the exits of the N/2 leaves using the reverse bit order
 *      of A[]. As a side note, the number of state changes is bounded by
 *      O(N * log_2(N)), so the limit of P is easily satisfied. (Well, the limit is
 *      there just for the grader~)
 * [Non-perfect tree] Then, I realized that this tree form isn't limited to perfect
 *      binary trees. Note that the tree can be defined in a recursive way. If a
 *      switch has to be responsible for N turns, we can create two new subtrees and
 *      point to them. The X subtree shall be responsible for ceil(N/2) turns, while
 *      the Y subtree shall be responsible for floor(N/2) turns. However, we quickly
 *      realize that this is impossible since each switch should return to state X
 *      when the ball completes a cycle. In the end, it seems that we still have to
 *      add "turns" that point back to the root of our tree, so we still need
 *      two_pow - 1 nodes...
 * [m=1] We have to create a circuit that passes trigger 1 exactly n times. Let
 *      two_pow = 2^(ceil(log_2(n))). It's clear that we can use two_pow-1 nodes to
 *      form a tree, with some leaf's exits pointing to the tree root instead of some
 *      trigger. But notice sth: some switches are unnecessary. If X and Y point to 
 *      two subtrees which are isomorphic, this switch isn't necessary, so this
 *      subtask can be solved with log_2(n) switches~
 * This idea of shrinking subtrees can be extended to the full solution. We first
 * order A[] in a modified version of reverse bit order. We put exits that point back
 * to the root "as left as possible" so that the "shrinking" effect can be maximised.
 * I know I've done a bad job describing this... Sorry~
 * 
 * Switches needed:   n - 1 + #ones_in_binary(two_pow - n),
 *                 two_pow = 2^(ceil(log_2(n))  (bound tight except for const term)
 * Implementation 1                 (Full solution, construction, binary tree)
*/

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

typedef std::vector<int>    vec;

const int INF = 0x3f3f3f3f;

int reverse(int t, int digits) {
    int res = 0;
    for (int d = 0; d < digits; d++)
        res |= (1 << (digits - 1 - d)) * ((t >> d) & 1);
    return res;
}


vec order;      // reverse bit order / exits for the leaves
vec X, Y;

// The index of the root is returned. *helper* is the num of helper exits.
int build_tree(int l, int r, int helper) {
    int m = r - l, mid = (l + r) / 2;
    if (m == 1)
        return order[l];    // Directly return the node. We don't have to create one.
    int x, y;
    if (helper >= m / 2)
        x = -INF, y = build_tree(mid, r, helper - m / 2);   // -INF: placeholder
    else
        x = build_tree(l, mid, helper), y = build_tree(mid, r, 0);
    X.push_back(x);
    Y.push_back(y);
    return -X.size();
}

void create_circuit(int m, vec A) {
    int n = A.size();
    A.push_back(0);

    int pow = 0, two_pow = 1;
    while (two_pow < n)
        pow++, two_pow *= 2;
    int helpers = two_pow - n;
    // reverse bit order, impl inspired by cp-algorithms.com/algebra/fft.html
    order.resize(two_pow);
    for (int i = 0, j = 1; i < two_pow; i++) {
        int rev = reverse(i, pow);
        order[rev] = (rev >= helpers ? A[j++] : -INF);  // -INF: placeholder for root
    }
    int tree_root = build_tree(0, two_pow, helpers);
    std::replace(X.begin(), X.end(), -INF, tree_root);
    std::replace(Y.begin(), Y.end(), -INF, tree_root);
    vec C(m + 1, tree_root);
    C[0] = A[0];
    assert(int(X.size()) == n - 1 + __builtin_popcount(two_pow - n));
    answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 4712 KB Output is correct
3 Correct 28 ms 5316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 12 ms 1364 KB Output is correct
6 Correct 49 ms 7632 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 4712 KB Output is correct
3 Correct 28 ms 5316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 12 ms 1364 KB Output is correct
6 Correct 49 ms 7632 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 43 ms 8388 KB Output is correct
9 Correct 52 ms 9464 KB Output is correct
10 Correct 72 ms 12892 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 27 ms 4712 KB Output is correct
3 Correct 28 ms 5316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 12 ms 1364 KB Output is correct
6 Correct 49 ms 7632 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 43 ms 8388 KB Output is correct
9 Correct 52 ms 9464 KB Output is correct
10 Correct 72 ms 12892 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 66 ms 12244 KB Output is correct
15 Correct 46 ms 8200 KB Output is correct
16 Correct 67 ms 11900 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 68 ms 12432 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 292 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 38 ms 6828 KB Output is correct
3 Correct 46 ms 6948 KB Output is correct
4 Correct 58 ms 10068 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 38 ms 6828 KB Output is correct
3 Correct 46 ms 6948 KB Output is correct
4 Correct 58 ms 10068 KB Output is correct
5 Correct 66 ms 11668 KB Output is correct
6 Correct 66 ms 11236 KB Output is correct
7 Correct 65 ms 11392 KB Output is correct
8 Correct 60 ms 11028 KB Output is correct
9 Correct 41 ms 7028 KB Output is correct
10 Correct 59 ms 10896 KB Output is correct
11 Correct 60 ms 10488 KB Output is correct
12 Correct 41 ms 7252 KB Output is correct
13 Correct 40 ms 7364 KB Output is correct
14 Correct 44 ms 7980 KB Output is correct
15 Correct 67 ms 7996 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 37 ms 7064 KB Output is correct
18 Correct 38 ms 6980 KB Output is correct
19 Correct 45 ms 7236 KB Output is correct
20 Correct 60 ms 10744 KB Output is correct
21 Correct 64 ms 10488 KB Output is correct
22 Correct 61 ms 10492 KB Output is correct