fork download
copy 
  1. #include<iostream>
  2. #include<math.h>
  3. #include<algorithm>
  4. #include<string.h>
  5. #include<map>
  6. #include<vector>
  7. #include<queue>
  8. #include<list>
  9. #include<set>
  10. //#include<bits/stdc++.h>
  11.  
  12. #define ll long long
  13. #define fi first
  14. #define se second
  15. #define ii pair<int,int>
  16. #define BIT(x,i) (x & (1 << i))
  17. #define MASK(x) (1 << x)
  18.  
  19. using namespace std;
  20.  
  21. const int N = 2e6+7;
  22. const int inf = 1e9 + 7;
  23. const long long infll = 1e18;
  24. const int MOD = 998244353;
  25.  
  26. long long n,k;
  27. int a[N], bit[N], ok[N];
  28.  
  29. void update(int x, int v) {
  30.     while(x <= n) {
  31.         bit[x] += v;
  32.         x += (x&-x);
  33.     }
  34. }
  35. int get(int l,int r) {
  36.     int ans = 0;
  37.     while(l <= r) {
  38.         if(r - (r&-r) >= l) {
  39.             ans += bit[r];
  40.             r -= (r&-r);
  41.         } else {
  42.             ans += a[r];
  43.             r--;
  44.         }
  45.     }
  46.     return ans;
  47. }
  48. int solve_case1(int i, int sum) {
  49.     int l = i + 1;
  50.     int r = n;
  51.     if(l > r) return 0;
  52.     int pos;
  53.     while(l <= r) {
  54.         int mid = (l + r) / 2;
  55.         if(get(i + 1, mid) + sum >= k) {
  56.             pos = mid;
  57.             r = mid - 1;
  58.         } else l = mid + 1;
  59.     }
  60.     return pos;
  61. }
  62. int solve_case2(int i,int suf) {
  63.     int l = 1;
  64.     int r = i - 1;
  65.     if(l > r) return 0;
  66.     int pos;
  67.     while(l <= r) {
  68.         int mid = (l + r) / 2;
  69.         if(suf + get(1, mid) >= k) {
  70.             pos = mid;
  71.             r = mid - 1;
  72.         } else l = mid + 1;
  73.     }
  74.     return pos;
  75. }
  76. int solve_case3(int i, int pre, int suf) {
  77.     int l = 1;
  78.     int r = n;
  79.     int cnt;
  80.     while(l <= r) {
  81.         int mid = (l + r) / 2;
  82.         if((pre + suf) * mid <= k) {
  83.             cnt = mid;
  84.             l = mid + 1;
  85.         }  else r = mid - 1;
  86.     }
  87.     if((pre + suf) * cnt == k) {
  88.         if(pre == 0) return solve_case1(i, (pre + suf) * (cnt - 1));
  89.         return solve_case2(i, (pre + suf) * cnt - pre); 
  90.     } else
  91.     if((pre + suf) * cnt + suf >= k) return solve_case1(i, (pre + suf) * cnt);   
  92.     return solve_case2(i, (pre + suf) * cnt + suf);
  93. }
  94. int main()
  95. {
  96.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  97.     // freopen("test.inp","r",stdin);
  98.     // freopen("test.out","w",stdout);
  99.     cin>>n>>k;
  100.     for(int i=1;i<=n;i++) {
  101.         a[i] = 1;
  102.         update(i, 1);
  103.     }
  104.  
  105.     k++;
  106.     int kk = k;
  107.     int i;
  108.     if(k % n == 0) i = n; else i = k % n;
  109.     for(int j=1;j<n;j++) {
  110.         cout<<i<<" "; ok[i] = 1;
  111.         k = kk % (n - j);
  112.         if(k == 0) k = n-j;
  113.         int suf = get(i + 1, n);
  114.         int pre = get(1 , i - 1);
  115.         update(i, -1);
  116.         a[i] = 0;
  117.         if(suf >= k) i = solve_case1(i,0); 
  118.         else if(pre + suf >= k) i = solve_case2(i, suf);
  119.         else i = solve_case3(i, pre, suf);
  120.     }
  121.     for(int i=1;i<=n;i++) if(ok[i] == 0) cout<<i;
  122.     return 0; 
  123. }
Runtime error #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hkmoRx
language:
C++ (gcc 8.3)
created:
277 days 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!