This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include "interactive.h"
using namespace std;
const int maxn=105;
int a[maxn];
int lft[maxn],rgt[maxn];
set<int>arr[2*maxn];
vector<int>fn;
map<int,vector<int>>m;
void f(int l,int r,int nd,int lev){
lft[nd] = l;
rgt[nd] = r;
m[lev].push_back(nd);
if(l == r){
fn.push_back(nd);
return;
}
int md = (l + r) / 2;
f(l,md,nd*2,lev+1);
f(md+1,r,nd*2+1,lev+1);
}
set<int>A(vector<int>v){
if(v.empty()) return set<int>();
// for(auto i : v) cout<<i<<' ';
// cout<<" ----> ";
vector<int>now = v;
now.push_back(1);
vector<int>nw = get_pairwise_xor(now);
vector<int>z = get_pairwise_xor(v);
multiset<int>SS(nw.begin(),nw.end());
for(auto i : z) SS.erase(i);
set<int>jg;
for(auto i : SS) jg.insert(i ^ a[1]);
jg.erase(0);
// for(auto i : jg) cout<<i<<' ';
// cout<<'\n';
return jg;
}
vector<int> guess(int n) {
a[1] = ask(1);
f(2,n,1,1);
for(auto i : m){
vector<int>now;
for(auto j : i.second){
if(j & 1) for(int k = lft[j];k <= rgt[j];k++){
now.push_back(k);
}
}
set<int>sw = A(now);
if(i.first == 1){
arr[1] = sw;
continue;
}
for(auto j : i.second){
if(!(j & 1)){
arr[j] = arr[j/2];
for(auto l : arr[j+1]) arr[j].erase(l);
}
else {
for(auto l : arr[j/2]) if(sw.find(l) != sw.end()) arr[j].insert(l);
}
}
}
// for(auto i : arr[1]) cout<<i<<' ';
// cout<<'\n';
vector<int>ans; ans.push_back(a[1]);
for(auto i : fn) ans.push_back(*arr[i].begin());
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |