Advertisement
mohammedehab2002

Untitled

Jun 13th, 2020
1,579
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 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 z[11],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 get(int i,int sup)
  15. {
  16.     int ans=sup;
  17.     for (int b=0;b<11;b++)
  18.     {
  19.         if (ans&(1<<b))
  20.         {
  21.             if (z[b]!=i)
  22.             ans&=query(i,z[b]);
  23.             else
  24.             ans^=(1<<b);
  25.         }
  26.     }
  27.     return ans;
  28. }
  29. int main()
  30. {
  31.     int n;
  32.     scanf("%d",&n);
  33.     memset(z,-1,sizeof(z));
  34.     while (count(z,z+11,-1))
  35.     {
  36.         int i=uniform_int_distribution<int>(1,n)(rng),j=uniform_int_distribution<int>(1,n)(rng);
  37.         if (i==j)
  38.         continue;
  39.         int tmp=query(i,j);
  40.         for (int b=0;b<11;b++)
  41.         {
  42.             if (!(tmp&(1<<b)))
  43.             z[b]=i;
  44.         }
  45.     }
  46.     vector<int> qp;
  47.     for (int i=1;i<=n;i++)
  48.     qp.push_back(i);
  49.     shuffle(qp.begin(),qp.end(),rng);
  50.     int idx=-1,val=(1<<11)-1;
  51.     for (i:qp)
  52.     {
  53.         if (idx==-1 || query(idx,i)==val)
  54.         {
  55.             idx=i;
  56.             val=get(i,val);
  57.         }
  58.     }
  59.     for (int i=1;i<=n;i++)
  60.     {
  61.         if (i!=idx)
  62.         p[i]=query(i,idx);
  63.     }
  64.     printf("!");
  65.     for (int i=1;i<=n;i++)
  66.     printf(" %d",p[i]);
  67.     printf("\n");
  68.     fflush(stdout);
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement