Submission #827782

#TimeUsernameProblemLanguageResultExecution timeMemory
827782WLZMechanical Doll (IOI18_doll)C++17
84 / 100
116 ms15868 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; struct node { int idx, state; node *left, *right; }; int n, m, cur_idx = 0, max_depth = 0, next_power = 1; vector<int> a, c, x, y; set<int> removed_bits; node *build(int l, int r, int pw, int depth = 0) { max_depth = max(max_depth, depth); if (pw == 1) return nullptr; if (((next_power - n) & pw) && !removed_bits.count(pw)) { removed_bits.insert(pw); return nullptr; } x.push_back(-1); y.push_back(-1); node *ans = new node{cur_idx++, 0, nullptr, nullptr}; ans->left = build(l, r - pw / 2, pw / 2, depth + 1); ans->right = build(r - pw / 2 + 1, r, pw / 2, depth + 1); if (ans->left != nullptr) x[ans->idx] = -(ans->left->idx + 1); if (ans->right != nullptr) y[ans->idx] = -(ans->right->idx + 1); return ans; } void create_circuit(int M, std::vector<int> A) { n = (int) A.size(), m = M, a = A; c.resize(m + 1); c[0] = a[0]; for (int i = 1; i <= M; i++) c[i] = -1; a.erase(a.begin()); a.push_back(0); while (next_power < n) next_power *= 2; node *root = build(0, n - 1, next_power); node *cur = root; int ptr = 0; bool first = n % 2; while (ptr < n) { int depth = 1; while ((cur->state == 0 && cur->left != nullptr) || (cur->state == 1 && cur->right != nullptr)) { depth++; cur->state = !cur->state; if (cur->state == 1) cur = cur->left; else cur = cur->right; } if (depth == max_depth && ptr < n) { if (!first) { if (cur->state == 0) x[cur->idx] = a[ptr++]; else y[cur->idx] = a[ptr++]; } first = false; } cur->state = !cur->state; cur = root; } answer(c, x, y); }
#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...