This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |