#include <bits/stdc++.h>
#include "interactive.h"
using namespace std;
int a0;
vector<int> All;
struct state
{
int l, r;
vector<int> lhs, rhs, mems;
state(int l, int r) : l(l), r(r) {}
};
vector<int> get_all(vector<int> v)
{
vector<int> ret = get_pairwise_xor(v);
for (auto u : v)
assert(u != 1);
v.push_back(1);
vector<int> ret2 = get_pairwise_xor(v);
sort(ret.begin(), ret.end());
sort(ret2.begin(), ret2.end());
multiset<int> mu;
vector<int> ret3;
for (auto u : ret2)
mu.insert(u);
for (auto u : ret)
mu.erase(mu.find(u));
for (auto u : mu)
if (u)
ret3.push_back(u ^ a0);
sort(ret3.begin(), ret3.end());
ret3.erase(unique(ret3.begin(), ret3.end()), ret3.end());
return ret3;
}
vector<int> query(vector<int> v)
{
v.push_back(a0);
v = get_pairwise_xor(v);
vector<int> ret ;
for(auto u : v){
int x = u^a0 ;
if(x != a0 && binary_search(All.begin() , All.end() , x)){
ret.push_back(x) ;
}
}
return ret;
}
vector<int> guess(int n)
{
vector<int> ans;
a0 = ask(1);
if (n == 1)
return {a0};
ans.resize(n - 1);
iota(ans.begin(), ans.end(), 2);
ans = get_all(ans);
vector<state> stt;
stt.push_back(state(1, n));
ans.push_back(a0);
stt.back().mems = ans;
All = ans;
sort(All.begin(), All.end());
while (stt.size())
{
bool flag = 1;
vector<int> lhs, rhs;
vector<state> stt2;
for (auto u : stt)
{
if (u.l != u.r)
flag = 0;
if (u.l == u.r)
{
stt2.push_back(u);
continue;
}
int mid = (u.l + u.r) >> 1;
for (int j = mid + 1; j <= u.r; ++j)
rhs.push_back(j);
stt2.push_back(state(u.l, mid));
stt2.push_back(state(mid + 1, u.r));
}
rhs = query(rhs);
sort(rhs.begin(), rhs.end());
auto isR = [&](int x) -> bool {
if (binary_search(rhs.begin(), rhs.end(), x))
return 1;
return 0;
};
int j = 0;
for (int i = 0; i < stt.size(); ++i)
{
if (stt[i].l == stt[i].r)
{
++j;
}
else
{
for (auto u : stt[i].mems)
{
if (isR(u))
stt2[j + 1].mems.push_back(u);
else
stt2[j].mems.push_back(u);
}
j += 2;
}
}
stt = stt2;
if (stt.size() == n)
break;
}
ans.clear();
for (auto u : stt)
ans.push_back(u.mems.back());
return ans;
}
Compilation message
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:97:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 0; i < stt.size(); ++i)
| ~~^~~~~~~~~~~~
Xoractive.cpp:116:30: warning: comparison of integer expressions of different signedness: 'std::vector<state>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
116 | if (stt.size() == n)
| ~~~~~~~~~~~^~~~
Xoractive.cpp:70:20: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
70 | bool flag = 1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Not correct position |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
876 KB |
Not correct position |
| 2 |
Halted |
0 ms |
0 KB |
- |
