oj.uz

Submission #426549

# Submission time Handle Problem Language Result Execution time Memory
426549 2021-06-14T06:19:35 Z KoD Mechanical Doll (IOI18_doll) C++17
100 / 100
 412 ms 25068 KB 
#include <bits/extc++.h>
#include "doll.h"

namespace {
    
template <class T> using Vec = std::vector<T>;
template <class T, class U> using HashTable = __gnu_pbds::gp_hash_table<T, U>;

int get_id() {
    static int id = 0;
    id -= 1;
    return id;
}

}

void create_circuit(int M, Vec<int> A) {
    A.push_back(0);
    const int N = (int) A.size();
    Vec<Vec<int>> graph_(N + M + 1 + 20);
    auto graph = graph_.begin() + N + 20;
    for (int i = 1; i <= M; ++i) {
        graph[i].push_back(-1);
    }
    {
        int H = 0;
        while ((1 << H) < N) {
            H += 1;
        }
        int M = N, last = 0;
        while ((1 << H) != M) {
            const int S = 1 << (H - 1);
            M -= S;
            Vec<int> id(S);
            for (int i = 0; i < S; ++i) {
                id[i] = get_id();
            }
            graph[last].push_back(id[0]);
            last = id[0];
            graph[last].push_back(id[1]);
            for (int i = S / 2 - 1; i > 0; --i) {
                graph[id[i]].push_back(id[2 * i]);
                graph[id[i]].push_back(id[2 * i + 1]);
            }
            H -= 1;
            const int root = last;
            while ((1 << (H - 1)) >= M) {
                const int u = get_id();
                graph[last].push_back(u);
                graph[u].push_back(-1);
                last = u;
                H -= 1;
            }
        }
        if (M > 1) {
            int S = M;
            Vec<int> id(M);
            for (int i = 1; i < S; ++i) {
                id[i] = get_id();
            }
            graph[last].push_back(id[1]);
            for (int i = S / 2 - 1; i > 0; --i) {
                graph[id[i]].push_back(id[2 * i]);
                graph[id[i]].push_back(id[2 * i + 1]);
            }
        }
    }
    Vec<int> idx(N + 20);
    for (int i = 0; i < N; ++i) {
        int x = -1;
        while (true) {
            idx[-x] ^= 1;
            if ((int) graph[x].size() <= (idx[-x] ^ 1)) {
                break;
            }
            x = graph[x][idx[-x] ^ 1];
        }
        graph[x].push_back(A[i]);
    }
    const int S = -(get_id() + 1);
    Vec<int> C(M + 1), X(S), Y(S);
    for (int i = 0; i <= M; ++i) {
        C[i] = graph[i][0];
    }
    for (int i = 0; i < S; ++i) {
        X[i] = graph[-i - 1][0];
        Y[i] = graph[-i - 1][1];
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, {anonymous}::Vec<int>)':
doll.cpp:46:23: warning: unused variable 'root' [-Wunused-variable]
   46 |             const int root = last;
      |                       ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 85 ms 12776 KB Output is correct
3 Correct 95 ms 10532 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 22 ms 6860 KB Output is correct
6 Correct 155 ms 15880 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 85 ms 12776 KB Output is correct
3 Correct 95 ms 10532 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 22 ms 6860 KB Output is correct
6 Correct 155 ms 15880 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 194 ms 16416 KB Output is correct
9 Correct 224 ms 18720 KB Output is correct
10 Correct 412 ms 24844 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 85 ms 12776 KB Output is correct
3 Correct 95 ms 10532 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 22 ms 6860 KB Output is correct
6 Correct 155 ms 15880 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 194 ms 16416 KB Output is correct
9 Correct 224 ms 18720 KB Output is correct
10 Correct 412 ms 24844 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 371 ms 24092 KB Output is correct
15 Correct 206 ms 15124 KB Output is correct
16 Correct 375 ms 23052 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 355 ms 25068 KB Output is correct
21 Correct 1 ms 288 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 208 ms 12008 KB Output is correct
3 Correct 169 ms 12084 KB Output is correct
4 Correct 384 ms 18208 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 208 ms 12008 KB Output is correct
3 Correct 169 ms 12084 KB Output is correct
4 Correct 384 ms 18208 KB Output is correct
5 Correct 364 ms 22296 KB Output is correct
6 Correct 331 ms 21236 KB Output is correct
7 Correct 375 ms 21592 KB Output is correct
8 Correct 359 ms 20436 KB Output is correct
9 Correct 231 ms 13020 KB Output is correct
10 Correct 392 ms 20212 KB Output is correct
11 Correct 336 ms 19688 KB Output is correct
12 Correct 201 ms 13004 KB Output is correct
13 Correct 195 ms 13944 KB Output is correct
14 Correct 189 ms 14328 KB Output is correct
15 Correct 213 ms 14708 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 182 ms 13064 KB Output is correct
18 Correct 190 ms 13024 KB Output is correct
19 Correct 168 ms 13044 KB Output is correct
20 Correct 405 ms 19988 KB Output is correct
21 Correct 294 ms 19688 KB Output is correct
22 Correct 371 ms 19796 KB Output is correct