Samkit5025

Untitled

Aug 19th, 2022
55
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.  
  4. struct cmp {
  5.     bool operator()(pair<int,int> const& a, pair<int,int> const& b)
  6.     {
  7.         if((a.second-a.first)!=(b.second-b.first))return (a.second-a.first)<(b.second-b.first);
  8.         if(a.first!=b.first)return a.first>b.first;
  9.         return true;
  10.     }
  11. };
  12.  
  13.  
  14. vector<int> findArray(int N){
  15.     vector<int> A(N);
  16.     priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
  17.     pq.push({0,N-1});
  18.     // int count = 1;
  19.     while(!pq.empty()){
  20.         auto temp = pq.top();
  21.         pq.pop();
  22.  
  23.         int len = temp.second-temp.first+1;
  24.  
  25.         if(len&1){
  26.             int pivot = (temp.first + temp.second)/2;
  27.             A[pivot] = len;
  28.             if(pivot-temp.first){
  29.                 pq.push({temp.first,pivot-1});
  30.             }
  31.             if(temp.second-pivot){
  32.                 pq.push({pivot+1,temp.second});
  33.             }
  34.         }
  35.         else{
  36.             int pivot = (temp.first + temp.second-1)/2;
  37.             A[pivot] = len;
  38.             if(pivot-temp.first){
  39.                 pq.push({temp.first,pivot-1});
  40.             }
  41.             if(temp.second-pivot){
  42.                 pq.push({pivot+1,temp.second});
  43.             }
  44.         }
  45.     }
  46.     return A;
  47. }  
  48.  
  49. int main(){
  50.     int N;
  51.     cin>>N;
  52.     vector<int> A = findArray(N);
  53.  
  54.     for(int i=0;i<N;i++){
  55.         cout<<A[i]<<" ";
  56.     }
  57.     cout<<endl;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment