fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5.  
  6. const int N = 50005, M = 36;
  7. int ans[M+1][N<<2];
  8. int suf[M+1][N<<2];
  9. int pre[M+1][N<<2];
  10. vector<int> temp;
  11.  
  12. void build(int node, int l, int r)
  13. {
  14.     if(l == r)
  15.     {
  16.         ans[1][node] = 1;
  17.         pre[1][node] = 1;
  18.         suf[1][node] = 1;
  19.         return;
  20.     }
  21.     int mid = (l+r)>>1;
  22.     int left = node<<1;
  23.     int right = left + 1;
  24.     build(left, l, mid);
  25.     build(right, mid+1, r);
  26.  
  27.     for(int i = 1; i<M; i++)
  28.         ans[i][node] += ans[i][left] + ans[i][right];
  29.  
  30.     ans[1][node]++; // whole node
  31.  
  32.     for(int i = 1; i<M/2; i++)
  33.         for(int j = 1; j<M/2; j++)
  34.             ans[i+j][node] += suf[i][left]*pre[j][right];
  35.  
  36.     ans[2][node]--; // whole pre and whole suf
  37.  
  38.     for(int i = 1; i<M; i++)
  39.         pre[i][node] += pre[i][left];
  40.     for(int i = 1; i<M; i++)
  41.         pre[i+1][node] += pre[i][right];
  42.     pre[2][node]--;
  43.     pre[1][node]++;
  44.  
  45.     for(int i = 1; i<M; i++)
  46.         suf[i][node] += suf[i][right];
  47.     for(int i = 1; i<M; i++)
  48.         suf[i+1][node] += suf[i][left];
  49.     suf[2][node]--;
  50.     suf[1][node]++;
  51.  
  52.     return;
  53. }
  54.  
  55. signed main()
  56. {
  57.  
  58.     ios::sync_with_stdio(false);
  59.     cin.tie(0);
  60.  
  61.     //freopen("input10.txt", "r", stdin);
  62.     //freopen("output10.txt", "w", stdout);
  63.     int t;
  64.     cin>>t;
  65.     while(t--){
  66.  
  67.         memset(ans,0,sizeof ans);
  68.         memset(pre,0,sizeof pre);
  69.         memset(suf,0,sizeof suf);
  70.  
  71.         int n;
  72.         cin>>n;
  73.         build(1, 1, n);
  74.         bool flag = true;
  75.  
  76.         temp.clear();
  77.         for(int i = M-1; i>0; i--)
  78.         {
  79.             if(flag)
  80.             {
  81.                 if(ans[i][1] == 0)
  82.                     continue;
  83.                 flag = false;
  84.                 temp.pb(ans[i][1]);
  85.             }
  86.             else
  87.                 temp.pb(ans[i][1]);
  88.         }
  89.  
  90.         cout<<temp.size()<<endl;
  91.         for(int i = temp.size() - 1; i>=0; i--)
  92.             cout<<temp[i]<<" ";
  93.         cout<<endl;
  94.  
  95.     }
  96.     return 0;
  97. }
Success #stdin #stdout 0.04s 89848KB
comments (?)
stdin
copy 
2
3
5
stdout
copy 
2
5 1 
3
9 4 2
https://ideone.com/najIxh
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!