Advertisement
mohammedehab2002

Untitled

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