#include <bits/stdc++.h>
#include "interactive.h"
// #include "grader.cpp"
#define ok puts("ok");
using namespace std;
int pw[123];
vector <int> ar;
vector <int> vec[12345], vv[1234];
multiset <int> ss[1234];
int nn;
int Ask(int x) {
if (ar[x] != -1) return ar[x];
return ar[x] = ask(x + 1);
}
// BIG, SMALL
vector <int> get(int x, vector <int> pos1, vector<int> pos2) {
multiset <int> s;
for (int to : pos1) {
s.insert(to);
}
for (int to : pos2) {
s.erase(s.find(to));
}
vector <int> vec;
int c1 = 0;
for (int to : s) {
if (c1 & 1 ^ 1) {
vec.push_back(to ^ x);
}
c1++;
}
return vec;
}
// Big, SMALL
vector <int> ex(vector <int> p1, vector <int> p2) {
int c = 0;
vector <int> ans;
sort(p1.begin(), p1.end());
sort(p2.begin(), p2.end());
for (int to : p1) {
if (to == p2[c]) {
c++;
} else {
ans.push_back(to);
}
}
return ans;
}
// big, small
vector <int> in(vector <int> p2, vector <int> p1) {
int c = 0;
multiset <int> s;
vector <int> ans;
for (int to : p2) {
s.insert(to);
}
for (int to : p1) {
if (s.count(to)) {
ans.push_back(to);
s.erase(s.find(to));
}
}
return ans;
}
void go(int v, int l, int r, int lvl, int ind) {
/*
cout << v << ' ' << l << ' ' << r << ' ' << lvl << ' ' << ind << endl;
for (int to : vv[v]) {
cout << to << ' ';
}
cout << endl;
*/
int len = (1 << lvl - 1);
if (lvl == 0) {
ar[(1 << pw[nn - 1]) - 1 - ind] = vv[v][0];
return ;
}
vv[v + v] = in(vv[v], vec[lvl - 1]);
go(v + v, l, l + len - 1, lvl - 1, ind + len);
if (l + len < nn) {
vv[v + v + 1] = ex(vv[v], vv[v + v]);
go(v + v + 1, l + len, min(nn - 1, r), lvl - 1, ind);
}
}
vector<int> guess(int _n) {
nn = _n;
vector<int> forask[2];
ar.resize(nn, -1);
for (int i = 1; i <= nn; i++) {
pw[i] = pw[i / 2] + 1;
}
for (int i = pw[nn - 1]; i >= 0; i--) {
int lvl = (1 << i);
for (int k = 0; k < 2; k++)
forask[k].clear();
for (int j = 0; j < nn; j += lvl + lvl) {
for (int k = j; k < min(j + lvl, nn); k++) {
forask[0].push_back(k + 1);
if (k != 0)
forask[1].push_back(k + 1);
}
}
vec[i] = get(Ask(0), get_pairwise_xor(forask[0]), get_pairwise_xor(forask[1]));
for (int to : vec[i]) {
ss[i].insert(to);
}
}
vv[1] = vec[pw[n - 1]];
go(1, 0, n - 1, pw[n - 1], 0);
return ar;
}
Compilation message
Xoractive.cpp: In function 'std::vector<int> get(int, std::vector<int>, std::vector<int>)':
Xoractive.cpp:32:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if (c1 & 1 ^ 1) {
~~~^~~
Xoractive.cpp: In function 'std::vector<int> in(std::vector<int>, std::vector<int>)':
Xoractive.cpp:59:6: warning: unused variable 'c' [-Wunused-variable]
int c = 0;
^
Xoractive.cpp: In function 'void go(int, int, int, int, int)':
Xoractive.cpp:83:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
int len = (1 << lvl - 1);
~~~~^~~
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:119:17: error: 'n' was not declared in this scope
vv[1] = vec[pw[n - 1]];
^
Xoractive.cpp:119:17: note: suggested alternative: '_n'
vv[1] = vec[pw[n - 1]];
^
_n
