#include <bits/stdc++.h>
#include "interactive.h"
using namespace std;
#define ii pair<int,int>
#define vi vector<int>
#define sz(x) (int)x.size()
vi ans;
set<int>p[111];
map<int,int>cnt[111];
int t[111];
/*
int ask(int i){
return ans[i];
}
vi get_pairwise_xor(vi pos){
vi ret;
for(int x:pos){
for(int y:pos){
ret.emplace_back(ans[x]^ans[y]);
}
}
sort(ret.begin(),ret.end());
return ret;
}
*/
vi guess(int n){
vi res;
res.resize(n);
if(n<=15){
for(int i=0; i<15; i++)
res[i]=ask(i+1);
return res;
}
res[0]=(ask(1));
int k=-1;
while(n>=(1<<++k)){}
cerr<<k<<"\n";
for(int i=0; i<k; i++){
vi q;
for(int j=2; j<=n; j++){
if(j>>i&1)q.emplace_back(j);
}
vi qq = q;
vi qqq = get_pairwise_xor(q);
qq.emplace_back(1);
qq = get_pairwise_xor(qq);
qq.erase(qq.begin());
for(int x:qqq)
qq.erase(find(qq.begin(),qq.end(),x));
for(int ind:q){
for(int x:qq){
x=x^ans[0];
t[ind]++;
p[ind].insert(x);
cnt[ind][x]++;
}
}
}
/*
for(int i=2; i<=n; i++){
cerr<<i<<" "<<sz(p[i])<<": ";
for(int x:p[i])cerr<<"["<<x<<","<<cnt[i][x]<<"] ";
cerr<<"\n";
}
// */
priority_queue<ii,vector<ii>,greater<ii>>pq; //degree,ind
for(int i=2; i<=n; i++){
//cerr<<i<<" total: "<<t[i]<<"\n";
pq.emplace(t[i],i);
}
while(!pq.empty()){
int mx=0; vi val;
int curind=0;
vi hold;
while(sz(pq)){
ii now = pq.top();
int deg = now.first;
int ind = now.second;
pq.pop();
/*
cerr<<deg<<" - "<<ind<<"\n";
for(int x:p[ind])cerr<<x<<","<<cnt[ind][x]<<" ";
cerr<<"\n";
// */
mx=-1;
curind=ind;
for(int x:p[ind]){
if(cnt[ind][x]>mx){
mx=cnt[ind][x];
val = vi();
val.emplace_back(x);
}else if(cnt[ind][x]==mx){
val.emplace_back(x);
}
}
if(sz(val)==1)break;
else hold.emplace_back(ind);
}
//cerr<<mx<<": ";
mx = val[0];
res[curind-1]=mx;
//cerr<<curind<<" "<<mx<<" "<<cnt[curind][mx]<<"\n";
for(int i=2; i<=n; i++){
if(p[i].find(mx)!=p[i].end()){
t[i]-=cnt[i][mx];
p[i].erase(p[i].find(mx));
}
}
for(int x:hold){
pq.emplace(t[x],x);
}
/*
for(int i=2; i<=n; i++){
cerr<<i<<" total: "<<t[i]<<"\n";
}
// */
}
return res;
}
/*
int main(){
//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin>>n;
ans.emplace_back(0);
for(int i=0; i<n; i++){
int x; cin>>x;
ans.emplace_back(x);
}
cerr<<"done input"<<"\n";
vi ans2 = guess(n);
for(int x:ans2)cout<<x<<" ";
cout<<"\n";
return 0;
}
*/
Compilation message
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:82:8: warning: unused variable 'deg' [-Wunused-variable]
82 | int deg = now.first;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Not correct position |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
