#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 n;
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[n - 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 < n) {
vv[v + v + 1] = ex(vv[v], vv[v + v]);
go(v + v + 1, l + len, min(n - 1, r), lvl - 1, ind);
}
}
vector<int> guess(int _n) {
n = _n;
vector<int> forask[2];
ar.resize(n, -1);
for (int i = 1; i <= n; i++) {
pw[i] = pw[i / 2] + 1;
}
for (int i = pw[n - 1]; i >= 0; i--) {
int lvl = (1 << i);
for (int k = 0; k < 2; k++)
forask[k].clear();
for (int j = 0; j < n; j += lvl + lvl) {
for (int k = j; k < min(j + lvl, n); 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;
}
/*
20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
*/
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);
~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
2 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
2428 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
