Advertisement
vinayak7989

Untitled

Sep 28th, 2022
619
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.42 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define int               long long
  4. #define pb                push_back
  5. #define ppb               pop_back
  6. #define all(x)            (x).begin(),(x).end()
  7. #define uniq(v)           (v).erase(unique(all(v)),(v).end())
  8. #define sz(x)             (int)((x).size())
  9. #define f                 first
  10. #define s                 second
  11. #define pii               pair<int,int>
  12. #define rep(i,a,b)        for(int i = a; i < b; i++)
  13. #define repd(i,a,b)       for(int i = a; i >= b; i--)
  14. #define mem1(a)           memset(a, -1, sizeof(a))
  15. #define ppc               __builtin_popcount
  16. #define ppcll             __builtin_popcountll
  17. #define ll                long long
  18. #define ld                long double
  19.  
  20. template<typename T,typename U>istream& operator>>(istream& in,pair<T,U> &a){in>>a.f>>a.s;return in;}
  21. template<typename T,typename U>ostream& operator<<(ostream& out,pair<T,U> a){out<<'('<<a.f<<", "<<a.s<<')';return out;}
  22. template<typename T>ostream& operator<<(ostream&cout,vector<T>const&v){cout<<"[";rep(i,0,sz(v)){if(i)cout<<", ";cout<<v[i];}return cout<<"]";}
  23. template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
  24. template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
  25.  
  26. #ifndef ONLINE_JUDGE
  27. #define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
  28. template <typename Arg1>
  29. void __f(const char* name, Arg1&& arg1) {
  30.       cout << name << " : " << arg1 << std::endl;
  31. }
  32. template <typename Arg1, typename... Args>
  33. void __f(const char* names, Arg1&& arg1, Args&&... args) {
  34.       const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
  35. }
  36. #else
  37. #define dbg(...)
  38. #endif
  39.  
  40. const ld pi = 3.14159265358979323846;
  41. const char nl = '\n';
  42. const long long INF=1e18;
  43. const int32_t M=1e9+7;
  44. const int32_t MM=998244353;
  45.  
  46. const int N=1e6+5;      
  47. ll n, m, q, k, l, r, x, y, z, a[N], b[N], c[N];
  48. string s,t;
  49.  
  50. struct node {
  51.       int val;
  52.       node* left = nullptr;
  53.       node* right = nullptr;
  54.       node(int v) : val(v) {};
  55. };
  56.  
  57. node* build(int l, int r, vector<int>& a) {
  58.       if(l > r) return nullptr;
  59.       if(l == r) return new node(a[l]);
  60.      
  61.       int len = r-l+1;
  62.       int lg = __lg(len);
  63.       int lastLevel = 1 << lg, each = (1 << lg) - 1;
  64.       each /= 2;
  65.       int leftSize = each + min(lastLevel/2, len - 2*each - 1);
  66.       node* left = build(l, l + leftSize - 1, a);
  67.       node* right = build(l + leftSize + 1, r, a);
  68.       node* ret = new node(a[l + leftSize]);
  69.       ret->left = left;
  70.       ret->right = right;
  71.       return ret;
  72. }
  73.  
  74. void KSBR(){
  75.       cin >> n;
  76.       vector<int> a(n);
  77.       for(int &x : a) cin >> x;
  78.      
  79.       node* root = build(0, n-1, a);
  80.       queue<node*> q;
  81.       q.push(root);
  82.       while(sz(q)) {
  83.             int siz = q.size();
  84.             for(int i = 0; i < siz; i++) {
  85.                   node* cur = q.front(); q.pop();
  86.                   cout << cur->val << " ";
  87.                   if(cur->left) q.push(cur->left);
  88.                   if(cur->right) q.push(cur->right);
  89.             }
  90.             cout << nl;
  91.       }
  92. }
  93. signed main(){
  94.       ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  95.       #ifdef SIEVE
  96.             sieve();
  97.       #endif
  98.       #ifdef NCR
  99.             init();
  100.       #endif
  101.       int t = 1;
  102.       //cin>>t;
  103.       while(t--) {
  104.             KSBR();
  105.       }
  106. }                            
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement