Advertisement
momo2345

constructing the array

Aug 24th, 2020
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. // ********* Assalamualaikum****** IN the name of my Almighty****:):)***
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  5. #define endl "\n"
  6. #define f(i,a,b) for(int i=a;i< b;i++)
  7. #define ff(i,a,b) for(int i= a;i>=b;i--)
  8. #define T int t; cin >>t; while(t--)
  9. #define vi vector<int>
  10. #define vll vector<long long>
  11. #define vs vector<string>
  12. #define vp vector<pair
  13. #define pii pair<int,int>
  14. #define pb push_back
  15. #define mk make_pair
  16. #define b(a) a.begin(),a.end()
  17. #define rb(a) a.rbegin(),a.rend()
  18. #define I int
  19. #define ll long long
  20. #define st string
  21. #define C char
  22. #define mn int main()
  23. #define fa(u,v) for(auto u:v)
  24. const I mx=2e5+123;
  25. I a[mx];
  26. mn
  27. {
  28. suni;
  29. T{
  30. int c=1;
  31. priority_queue<pii>p;
  32. I n;
  33. cin>>n;
  34. p.push({n,-1});
  35. while(!p.empty()){
  36. int l=p.top().second*(-1);
  37. int len= p.top().first;
  38. p.pop();
  39. int mid;
  40. int r=l+len-1;
  41. if(len%2) mid=(r+l)/2;
  42. else mid=(r+l-1)/2;
  43. a[mid]=c;
  44. c++;
  45. int l1,l2,r1,r2;
  46. l1=l;
  47. r1=mid-1;
  48. l2=mid+1;
  49. r2=r;
  50. if(l1<=r1) p.push({(r1-l1+1),-l1});
  51. if(l2<=r2) p.push({(r2-l2+1),-l2});
  52.  
  53. }
  54. for(int i=1;i<=n;i++) cout<<a[i]<<" ";
  55. cout<<endl;
  56.  
  57. }
  58. }
  59. //*******Happy Coding*******???******
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement