oj.uz

Submission #773273

# Submission time Handle Problem Language Result Execution time Memory
773273 2023-07-04T18:27:57 Z _martynas Mechanical Doll (IOI18_doll) C++11
76.5915 / 100
 154 ms 20852 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(sz_l == sz && sz != (1 << depth)) {
        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);

//        if((sz & (-sz)) != sz)
//            cerr << sz << " at depth " << depth<< " -> " << sz-sz_l << " " << sz_l << "\n";
//        if((sz & (-sz)) != sz)
//            cerr << temp << " & " << counter-prev-temp << " created\n";
    }

    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);
    cerr << counter << "?!\n";
    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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 35 ms 8092 KB Output is correct
3 Correct 35 ms 7668 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Incorrect 56 ms 11516 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 35 ms 8092 KB Output is correct
3 Correct 35 ms 7668 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Incorrect 56 ms 11516 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 35 ms 8092 KB Output is correct
3 Correct 35 ms 7668 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Incorrect 56 ms 11516 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #5
16.1998998858 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 64 ms 13472 KB Output is correct
3 Correct 75 ms 13516 KB Output is correct
4 Partially correct 143 ms 20332 KB Output is partially correct

Subtask #6
50.3916245616 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 64 ms 13472 KB Output is correct
3 Correct 75 ms 13516 KB Output is correct
4 Partially correct 143 ms 20332 KB Output is partially correct
5 Partially correct 154 ms 20852 KB Output is partially correct
6 Partially correct 131 ms 20548 KB Output is partially correct
7 Partially correct 126 ms 20684 KB Output is partially correct
8 Partially correct 120 ms 20408 KB Output is partially correct
9 Correct 68 ms 13444 KB Output is correct
10 Partially correct 122 ms 20460 KB Output is partially correct
11 Partially correct 119 ms 20292 KB Output is partially correct
12 Correct 69 ms 13520 KB Output is correct
13 Correct 66 ms 13728 KB Output is correct
14 Correct 85 ms 13748 KB Output is correct
15 Correct 67 ms 13740 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 64 ms 13556 KB Output is correct
18 Correct 65 ms 13520 KB Output is correct
19 Correct 67 ms 13552 KB Output is correct
20 Partially correct 120 ms 20340 KB Output is partially correct
21 Partially correct 120 ms 20316 KB Output is partially correct
22 Partially correct 114 ms 20268 KB Output is partially correct