#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using bdata = vector<bool>;
using di = pair<int, int>;
using vd = vector<di>;
struct SegTree {
idata treeIds;
int rsize = 0;
int start, height, size;
void generate (int node, int limit, int end) {
if (node == 0) return ;
generate(node >> 1, (limit + 1) >> 1, end >> 1);
if (node == start) return ;
for (int u = end - limit; u < end; u ++)
treeIds[u] = - ((rsize ++) + 1);
}
int getId (int node) {
int count = 0;
int diam = height - 1;
while (node != 1) {
if (node & 1) count += 1 << diam;
diam --;
node >>= 1;
}
return count;
}
idata X, Y;
SegTree (idata A) {
size = A.size();
height = ceil(log2(size));
start = 1 << height;
treeIds.resize(start << 1, - 1e9);
generate(start, size, treeIds.size());
vd g_pos;
for (int i = treeIds.size() - size; i < treeIds.size(); i ++)
g_pos.push_back({ getId( i ), i });
sort(g_pos.begin(), g_pos.end());
for (int i = 0; i < size; i ++)
treeIds[g_pos [i].second] = A[i]
X.resize(rsize); Y.resize(rsize);
for (int i = 1; i < start; i ++) {
if (treeIds[i] >= 0 || treeIds[i] == - 1e9) continue ;
int xid = - (1 + treeIds[i]);
int n0 = 2 * i; int vn0 = treeIds[n0] == - 1e9 ? -1 : treeIds[n0];
int n1 = 2 * i + 1; int vn1 = treeIds[n1] == - 1e9 ? -1 : treeIds[n1];
X[xid] = vn0;
Y[xid] = vn1;
}
}
};
void create_circuit(int M, vector<int> A) {
A.push_back(0);
idata C( M + 1, - 1 ); // - 1 is the decision tree root
SegTree tree(A);
idata X = tree.X;
idata Y = tree.Y;
answer(C, X, Y);
}
Compilation message
doll.cpp: In constructor 'SegTree::SegTree(idata)':
doll.cpp:52:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = treeIds.size() - size; i < treeIds.size(); i ++)
| ~~^~~~~~~~~~~~~~~~
doll.cpp:58:39: error: expected ';' before 'X'
58 | treeIds[g_pos [i].second] = A[i]
| ^
| ;
59 |
60 | X.resize(rsize); Y.resize(rsize);
| ~
