fork download
copy 
  1. #include <cstdio>
  2.  
  3. int tree[1<<23];
  4. int n,k, ans;
  5.  
  6. inline void init_tree(){
  7.     for(int i=n; i<2*n; ++i){
  8.         tree[i]=1;
  9.     }
  10.     for(int i=n-1; i; --i){
  11.         int j=i<<1;
  12.         tree[i]=tree[j]+tree[j|1];
  13.     }
  14.     return;
  15. }
  16.  
  17. int find_kth(int k, int v=1){
  18.    if(v>=n){
  19.        return v-n+1;
  20.    }
  21.    int left=v<<1, left_value=tree[left];
  22.    if(left_value>=k){
  23.        return find_kth(k, left);
  24.    }
  25.    return find_kth(k-left_value, left|1);
  26. }
  27.  
  28. void decrement(int pos){
  29.      pos+=n-1;
  30.      while(pos){
  31.         --tree[pos];
  32.         pos>>=1;
  33.      }
  34. }
  35.  
  36. int main(){
  37.     scanf("%d%d",&n,&k);
  38.     init_tree();
  39.     int k2=k-2;
  40.     int cur=1;
  41.     int shift=find_kth(1);
  42.     for(int i=1; i<=n; ++i){
  43.         cur=1+(cur+k2)%(n-i+1);
  44.         int x=find_kth(cur);
  45.         int real_x=(x-shift+n)%n+1;
  46.         decrement(x);
  47.         int y=real_x-i;
  48.         int mask=y>>31;
  49.         ans^=(y+mask)^mask;
  50.     }
  51.     printf("%d",ans);
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 48832KB
comments (?)
stdin
copy 
5 3
stdout
copy 
2
https://ideone.com/gDUbSD
language:
C++14 (gcc 8.3)
created:
7 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!