#include "doll.h"
#include <iostream>
#include <algorithm>
using namespace std;
bool used[400000];
int map[400000];
void print_tree(int i, int indent, vector<int> &x, vector<int> &y) {
if (i >= x.size()) return;
cerr << string(indent*2, ' ') << -i << ": x = " << x[i-1] << " y = " << y[i-1] << " used = " << used[i-1] << endl;
print_tree(i*2, indent+1, x, y);
print_tree(i*2+1, indent+1, x, y);
}
int get_num(int i, int d, int acc) {
if (d == 0) return acc;
return get_num(i / 2, d-1, acc*2 + i%2);
}
void create_circuit(int m, vector<int> a) {
vector<int> c(m + 1, -1);
c[0] = a[0];
int n = a.size();
if (n == 1) {
c[a[0]] = 0;
answer(c, {}, {});
return;
}
a.push_back(0);
a.erase(a.begin());
int n = 1;
int d = 0;
while (n < n) {
n *= 2;
d++;
}
int skip = n - n;
vector<int> x(n, -1), y(n, -1);
for (int i = 1; i < n/2; i++) {
x[i-1] = -i*2;
y[i-1] = -i*2 - 1;
}
vector<pair<int, int>> order;
for (int i = skip; i < n; i++) {
used[n/2 - 1 + i/2] = true;
order.push_back({get_num(i, d, 0), i});
}
sort(order.begin(), order.end());
for (int i = skip; i < n; i++) {
int j = order[i - skip].second;
int path = a[i - skip];
if (j % 2 == 0)
x[n/2 - 1 + j/2] = path;
else
y[n/2 - 1 + j/2] = path;
}
for (int i = n/2-1; i > 0; i--)
used[i-1] = used[i*2-1] || used[i*2];
int map_count = 0;
for (int i = 0; i < n; i++) {
if (used[i]) {
map[i] = -map_count-1;
map_count++;
}
else {
map[i] = -1;
}
}
vector<int> x2(map_count), y2(map_count);
int mapi = 0;
for (int i = 0; i < n; i++) {
if (used[i]) {
x2[mapi] = x[i] < 0 ? map[-x[i]-1] : x[i];
y2[mapi] = y[i] < 0 ? map[-y[i]-1] : y[i];
mapi++;
}
}
//print_tree(1, 0, x, y);
answer(c, x2, y2);
}
Compilation message
doll.cpp: In function 'void print_tree(int, int, std::vector<int>&, std::vector<int>&)':
doll.cpp:11:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | if (i >= x.size()) return;
| ~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:36:9: error: redeclaration of 'int n'
36 | int n = 1;
| ^
doll.cpp:25:9: note: 'int n' previously declared here
25 | int n = a.size();
| ^
doll.cpp:38:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
38 | while (n < n) {
| ~ ^ ~
