#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 300010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N;
vi adj[maxn];
vector <int32_t> X,Y;
vi build_idx[19], rev_build_idx[19];
int lg2[maxn];
int32_t solve(int32_t x){
if (adj[x].size() == 1) return adj[x][0];
int sz = adj[x].size();
int build_sz = 1<<(63 - __buildin_clz(sz));
assert(adj[x].size() >= build_sz);
int offset = (int)X.size() - 1;
FOR(i,1,build_sz-1){
X.pb(0); Y.pb(0);
}
FOR(i,2,build_sz-1){
if (i&1) Y[i/2+offset] = i;
else X[i/2+offset] = i;
}
FOR(i,0,build_sz-1){
int idx = rev_build_idx[lg2[build_sz]][i] + build_sz;
if (idx & 1) Y[idx/2+offset] = adj[x].back();
else X[idx/2+offset] = adj[x].back();
adj[x].pop_back();
}
adj[x].pb(-(offset+1+1));
return solve(x);
}
void create_circuit(int32_t M, std::vector<int32_t> A) {
N = A.size();
std::vector<int32_t> C(M + 1);
FOR(i,0,N-2){
adj[A[i]].pb(A[i+1]);
}
adj[A[N-1]].pb(0);
FOR(i,1,M) reverse(all(adj[i]));
int x = 1;
FOR(i,0,18){
lg2[x] = i; x <<= 1;
}
build_idx[1].pb(0); build_idx[1].pb(1);
FOR(i,2,18){
aFOR(j, build_idx[i-1]) build_idx[i].pb(j), build_idx[i].pb(j+(1<<(i-1)));
}
FOR(i,1,18){
rev_build_idx[i] = vi(build_idx[i].size());
FOR(j,0,build_idx[i].size()-1) rev_build_idx[i][build_idx[i][j]] = j;
}
C[0] = A[0];
for (int i = 1; i <= M; ++i) if (!adj[i].empty()){
C[i] = solve(i);
}
answer(C, X, Y);
}
Compilation message
doll.cpp: In function 'int32_t solve(int32_t)':
doll.cpp:42:29: error: '__buildin_clz' was not declared in this scope; did you mean '__builtin_clz'?
42 | int build_sz = 1<<(63 - __buildin_clz(sz));
| ^~~~~~~~~~~~~
| __builtin_clz
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from doll.cpp:2:
doll.cpp:43:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
43 | assert(adj[x].size() >= build_sz);
| ~~~~~~~~~~~~~~^~~~~~~~~~~
