oj.uz

Submission #773275

# Submission time Handle Problem Language Result Execution time Memory
773275 2023-07-04T18:31:33 Z _martynas Mechanical Doll (IOI18_doll) C++11
100 / 100
 184 ms 21656 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

int counter = 0;
struct Node {
    array<Node*, 2> c = {nullptr, nullptr};
    int to = 0, idx = -1;
    bool terminal() {
        return c[0] == nullptr && c[1] == nullptr;
    }
};

Node* construct(int sz, int depth) {
    if(sz <= 0) return nullptr;
    Node* root = new Node();
    if(depth <= 0) return root;
    root->idx = ++counter;
    int sz_l = 1<<(31-__builtin_clz(sz));
    if((1 << (depth-1)) >= sz) {
        root->c[0] = nullptr;
        root->c[1] = construct(sz, depth-1);
    }
    else {
        if(sz_l == sz && sz > 1) sz_l /= 2;
        int prev = counter;
        root->c[0] = construct(sz-sz_l, depth-1);
        int temp = counter-prev;
        root->c[1] = construct(sz_l, depth-1);
    }
    return root;
}

// first time going to terminal node
void walk(Node* curr, Node* root, int target, vector<int> &X, vector<int> &Y) {
    Node* to = curr->c[curr->to];
    if(!to) {
        if(curr->to) Y[curr->idx-1] = -root->idx;
        else X[curr->idx-1] = -root->idx;
        curr->to ^= 1;
        walk(root, root, target, X, Y);
    }
    else if(to->terminal()) {
        if(curr->to) Y[curr->idx-1] = target;
        else X[curr->idx-1] = target;
        curr->to ^= 1;
    }
    else {
        if(curr->to) Y[curr->idx-1] = -to->idx;
        else X[curr->idx-1] = -to->idx;
        curr->to ^= 1;
        walk(to, root, target, X, Y);
    }
}

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    int depth = 31-__builtin_clz(N-1)+1;
    Node* root = construct(N, depth);
    vector<int> C(M+1);
    vector<int> X(counter, -10000), Y(counter, -10000);
    C[0] = A[0];
    for(int i = 1; i <= M; i++) C[i] = -1;
    for(int i = 1; i < N; i++) {
        walk(root, root, A[i], X, Y);
    }
    walk(root, root, 0, X, Y);
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'Node* construct(int, int)':
doll.cpp:29:13: warning: unused variable 'temp' [-Wunused-variable]
   29 |         int temp = counter-prev;
      |             ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 39 ms 7628 KB Output is correct
3 Correct 35 ms 7216 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 59 ms 10828 KB Output is correct
7 Correct 0 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 39 ms 7628 KB Output is correct
3 Correct 35 ms 7216 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 59 ms 10828 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 71 ms 14316 KB Output is correct
9 Correct 79 ms 14700 KB Output is correct
10 Correct 132 ms 21656 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 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 39 ms 7628 KB Output is correct
3 Correct 35 ms 7216 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 1364 KB Output is correct
6 Correct 59 ms 10828 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 71 ms 14316 KB Output is correct
9 Correct 79 ms 14700 KB Output is correct
10 Correct 132 ms 21656 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 184 ms 21264 KB Output is correct
15 Correct 68 ms 13908 KB Output is correct
16 Correct 122 ms 21040 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 124 ms 21424 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 300 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 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 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 82 ms 12536 KB Output is correct
3 Correct 66 ms 12608 KB Output is correct
4 Correct 124 ms 19024 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 82 ms 12536 KB Output is correct
3 Correct 66 ms 12608 KB Output is correct
4 Correct 124 ms 19024 KB Output is correct
5 Correct 146 ms 19568 KB Output is correct
6 Correct 123 ms 19240 KB Output is correct
7 Correct 131 ms 19392 KB Output is correct
8 Correct 125 ms 19192 KB Output is correct
9 Correct 66 ms 12620 KB Output is correct
10 Correct 165 ms 19176 KB Output is correct
11 Correct 116 ms 19016 KB Output is correct
12 Correct 69 ms 12616 KB Output is correct
13 Correct 66 ms 12704 KB Output is correct
14 Correct 67 ms 12756 KB Output is correct
15 Correct 74 ms 12844 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 63 ms 12620 KB Output is correct
18 Correct 62 ms 12616 KB Output is correct
19 Correct 87 ms 12616 KB Output is correct
20 Correct 135 ms 19036 KB Output is correct
21 Correct 119 ms 19024 KB Output is correct
22 Correct 120 ms 19028 KB Output is correct