Advertisement
mohammedehab2002

Untitled

Jun 13th, 2020
1,874
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  4. int n,p[(1<<11)+5];
  5. int query(int i,int j)
  6. {
  7.     printf("? %d %d\n",i,j);
  8.     fflush(stdout);
  9.     int ans;
  10.     scanf("%d",&ans);
  11.     assert(ans!=-1);
  12.     return ans;
  13. }
  14. int getzero(vector<int> v)
  15. {
  16.     if (v.size()==1)
  17.     return v[0];
  18.     if (v.size()==2)
  19.     {
  20.         while (1)
  21.         {
  22.             int i=uniform_int_distribution<int>(1,n)(rng);
  23.             if (i==v[0] || i==v[1])
  24.             continue;
  25.             int a=query(i,v[0]),b=query(i,v[1]);
  26.             if (a<b)
  27.             return v[0];
  28.             if (a>b)
  29.             return v[1];
  30.         }
  31.     }
  32.     int idx;
  33.     while (1)
  34.     {
  35.         int i=uniform_int_distribution<int>(0,v.size()-1)(rng),j=uniform_int_distribution<int>(0,v.size()-1)(rng);
  36.         if (i==j)
  37.         continue;
  38.         if ((1<<(2*__builtin_popcount(query(v[i],v[j]))-1))<=v.size())
  39.         {
  40.             idx=i;
  41.             break;
  42.         }
  43.     }
  44.     vector<int> res(v.size(),1e9),nv;
  45.     for (int i=0;i<v.size();i++)
  46.     {
  47.         if (i!=idx)
  48.         {
  49.             res[i]=query(v[i],v[idx]);
  50.             res[idx]=min(res[idx],res[i]);
  51.         }
  52.     }
  53.     for (int i=0;i<v.size();i++)
  54.     {
  55.         if (res[i]==res[idx])
  56.         nv.push_back(v[i]);
  57.     }
  58.     return getzero(nv);
  59. }
  60. int main()
  61. {
  62.     scanf("%d",&n);
  63.     vector<int> all;
  64.     for (int i=1;i<=n;i++)
  65.     all.push_back(i);
  66.     int idx=getzero(all);
  67.     for (int i=1;i<=n;i++)
  68.     {
  69.         if (i!=idx)
  70.         p[i]=query(i,idx);
  71.     }
  72.     printf("!");
  73.     for (int i=1;i<=n;i++)
  74.     printf(" %d",p[i]);
  75.     printf("\n");
  76.     fflush(stdout);
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement