Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int n,p[(1<<11)+5];
- int query(int i,int j)
- {
- printf("? %d %d\n",i,j);
- fflush(stdout);
- int ans;
- scanf("%d",&ans);
- assert(ans!=-1);
- return ans;
- }
- int getzero(vector<int> v)
- {
- if (v.size()==1)
- return v[0];
- if (v.size()==2)
- {
- while (1)
- {
- int i=uniform_int_distribution<int>(1,n)(rng);
- if (i==v[0] || i==v[1])
- continue;
- int a=query(i,v[0]),b=query(i,v[1]);
- if (a<b)
- return v[0];
- if (a>b)
- return v[1];
- }
- }
- int idx;
- while (1)
- {
- int i=uniform_int_distribution<int>(0,v.size()-1)(rng),j=uniform_int_distribution<int>(0,v.size()-1)(rng);
- if (i==j)
- continue;
- if ((1<<(2*__builtin_popcount(query(v[i],v[j]))-1))<=v.size())
- {
- idx=i;
- break;
- }
- }
- vector<int> res(v.size(),1e9),nv;
- for (int i=0;i<v.size();i++)
- {
- if (i!=idx)
- {
- res[i]=query(v[i],v[idx]);
- res[idx]=min(res[idx],res[i]);
- }
- }
- for (int i=0;i<v.size();i++)
- {
- if (res[i]==res[idx])
- nv.push_back(v[i]);
- }
- return getzero(nv);
- }
- int main()
- {
- scanf("%d",&n);
- vector<int> all;
- for (int i=1;i<=n;i++)
- all.push_back(i);
- int idx=getzero(all);
- for (int i=1;i<=n;i++)
- {
- if (i!=idx)
- p[i]=query(i,idx);
- }
- printf("!");
- for (int i=1;i<=n;i++)
- printf(" %d",p[i]);
- printf("\n");
- fflush(stdout);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement