fork(2) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int tree[200005];
  6. int a[200005],b[200005];
  7. int N;
  8.  
  9. int read(int indx){
  10.     int sum=0;
  11.     while(indx>0){
  12.         sum=sum+tree[indx];
  13.         indx-=(indx&(-indx));
  14.     }
  15.     return sum;
  16. }
  17. void update(int indx,int val){
  18.     while(indx<=N){
  19.         tree[indx]+=val;
  20.         indx+=(indx&(-indx));
  21.     }
  22. }
  23. int bin_search(int l,int r,int x)
  24. {
  25.     int m;
  26.     while(l<r){
  27.         m=(l+r)/2;
  28.         if(read(m)>=x){
  29.             r=m;
  30.         }
  31.         else
  32.             l=m+1;
  33.     }
  34.     return r;
  35. }
  36.  
  37. int main(int argc, char const *argv[])
  38. {
  39.       long long int m;
  40.     scanf("%d%lld",&N,&m);
  41.  
  42.  
  43.     a[N-1]=m-1;
  44.     for (int i = N-1; i >0; --i)
  45.     {
  46.         a[i-1]+=a[i]/(N-i);
  47.         a[i]%=(N-i);
  48.     }
  49.     a[0]%=N;
  50.  
  51.     memset(tree,0,sizeof(tree));
  52.     for (int i = 0; i <N; ++i)
  53.     {
  54.         update(i+1,1);
  55.     }
  56.     for (int i = 0; i <N; ++i)
  57.     {
  58.         a[i]=bin_search(1,N,a[i]+1)-1;
  59.         update(a[i] + 1, -1);   
  60.     }
  61.     for (int i = 0; i <N; ++i)
  62.     {
  63.         printf("%d ",a[i]+1);
  64.     }
  65.     printf("\n");
  66.     return 0;
  67. }
Success #stdin #stdout 0s 5444KB
comments (?)
stdin 
50 1000
stdout 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 45 47 46 49 48 50 44
https://ideone.com/yP5KuJ
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!