oj.uz

Submission #710487

# Submission time Handle Problem Language Result Execution time Memory
710487 2023-03-15T09:31:48 Z Cyanmond Mechanical Doll (IOI18_doll) C++17
100 / 100
 147 ms 11932 KB 
#include "doll.h"
#include <bits/stdc++.h>

void create_circuit(int M, std::vector<int> A) {
    int N = (int)A.size();
    ++N;
    A.push_back(0);
    // i -> 2 * i, 2 * i + 1
    int logn = 1;
    while ((1 << logn) < N) ++logn;
    const int s = 1 << logn;
    std::vector<bool> isUse(2 * s);
    auto dfs = [&](auto &&self, const int i) -> bool {
        if (i >= s) {
            return isUse[i] = (s - (i - s) - 1) < N;
        } else {
            const auto a = self(self, 2 * i), b = self(self, 2 * i + 1);
            return isUse[i] = a or b;
        }
    };
    dfs(dfs, 1);
    std::vector<int> ids;
    for (int i = 1; i < 2 * s; ++i) {
        if (isUse[i]) {
            ids.push_back(i);
        }
    }
    std::vector<int> X(s, -1), Y(s, -1);
    for (int i = 1; i < s; ++i) {
        if (isUse[i]) {
            X[i] = 2 * i;
            Y[i] = 2 * i + 1;
            auto itr = std::lower_bound(ids.begin(), ids.end(), X[i]);
            if (itr != ids.end() and *itr == X[i]) {
                X[i] = itr - ids.begin();
            } else {
                X[i] = 0;
            }
            itr = std::lower_bound(ids.begin(), ids.end(), Y[i]);
            if (itr != ids.end() and *itr == Y[i]) {
                Y[i] = itr - ids.begin();
            } else {
                Y[i] = 0;
            }
        }
    }
    {
        std::vector<int> x, y;
        for (int i = 1; i < s; ++i) {
            if (std::max(X[i], Y[i]) != -1) {
                x.push_back(X[i]);
                y.push_back(Y[i]);
            }
        }
        X = x;
        Y = y;
    }
    const int E = (int)X.size();
    std::vector<bool> state(E, true);
    std::vector<int> C(M + 1, -1);
    for (int j = 0; j < N; ++j) {
        int i = 0, p = -1;
        while (ids[i] < s) {
            const int nxt = state[i] ? X[i] : Y[i];
            state[i] = not state[i];
            p = i;
            i = nxt;
        }
        (state[p] ? Y[p] : X[p]) = -A[j] - 1;
    }
    for (int i = 0; i < E; ++i) {
        ++X[i];
        X[i] *= -1;
        ++Y[i];
        Y[i] *= -1;
    }
    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 53 ms 5300 KB Output is correct
3 Correct 50 ms 4900 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 65 ms 6680 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 53 ms 5300 KB Output is correct
3 Correct 50 ms 4900 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 65 ms 6680 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 92 ms 8488 KB Output is correct
9 Correct 99 ms 9024 KB Output is correct
10 Correct 145 ms 11932 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 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 53 ms 5300 KB Output is correct
3 Correct 50 ms 4900 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 65 ms 6680 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 92 ms 8488 KB Output is correct
9 Correct 99 ms 9024 KB Output is correct
10 Correct 145 ms 11932 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 122 ms 11368 KB Output is correct
15 Correct 84 ms 8036 KB Output is correct
16 Correct 140 ms 11168 KB Output is correct
17 Correct 1 ms 220 KB Output is correct
18 Correct 0 ms 304 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 128 ms 11768 KB Output is correct
21 Correct 1 ms 224 KB Output is correct
22 Correct 1 ms 300 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 87 ms 7704 KB Output is correct
3 Correct 77 ms 7744 KB Output is correct
4 Correct 136 ms 10092 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 87 ms 7704 KB Output is correct
3 Correct 77 ms 7744 KB Output is correct
4 Correct 136 ms 10092 KB Output is correct
5 Correct 147 ms 10952 KB Output is correct
6 Correct 122 ms 10680 KB Output is correct
7 Correct 135 ms 10764 KB Output is correct
8 Correct 111 ms 10412 KB Output is correct
9 Correct 76 ms 7696 KB Output is correct
10 Correct 113 ms 10300 KB Output is correct
11 Correct 112 ms 10140 KB Output is correct
12 Correct 73 ms 7700 KB Output is correct
13 Correct 84 ms 7836 KB Output is correct
14 Correct 84 ms 7860 KB Output is correct
15 Correct 79 ms 7896 KB Output is correct
16 Correct 2 ms 608 KB Output is correct
17 Correct 68 ms 6396 KB Output is correct
18 Correct 80 ms 7756 KB Output is correct
19 Correct 75 ms 7728 KB Output is correct
20 Correct 127 ms 10176 KB Output is correct
21 Correct 116 ms 10108 KB Output is correct
22 Correct 127 ms 10176 KB Output is correct