Submission #773275

#TimeUsernameProblemLanguageResultExecution timeMemory
773275_martynasMechanical Doll (IOI18_doll)C++11
100 / 100
184 ms21656 KiB
#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 (stderr)

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