fork(1) download
copy 
  1. #include<stdio.h>
  2. #define maxn 1100000
  3. int fenwick[maxn+1], n;
  4. inline void dec_after(int x){
  5.     while(1){
  6.         --fenwick[x];
  7.         x+=x&(-x);
  8.         if(x>n)
  9.             return;
  10.     }
  11. }
  12. inline void sum_before(int x, int &sum){
  13.     sum=0;
  14.     while(1){
  15.         sum+=fenwick[x];
  16.         if(x<=1)
  17.             return;
  18.         x-=(x)&(-x);
  19.     }
  20. }
  21. inline void find_kth(int k,int &res){
  22.     int up=n, low=1, cur;
  23.     while(1){
  24.         if(up==low){
  25.             res=low;
  26.             return;
  27.         }
  28.         int mid=(low+up)>>1;
  29.         sum_before(mid, cur);
  30.         if(cur+mid>=k)
  31.             up=mid;
  32.         else
  33.           low=mid+1;
  34.     }
  35. }
  36. int main(){
  37.     int k,cur=1,ans=0,x, i;
  38.     scanf("%d %d", &n, &k);
  39.     for(i=1; i<=n; ++i){
  40.         cur=1+(cur+k-2)%(n-i+1);
  41.         find_kth(cur,  x);
  42.         dec_after(x);
  43.         ans^=(i>=x)?(i-x):(x-i) ; 
  44.     }
  45.     printf("%d\n", ans);
  46.     return 0;
  47. }
Success #stdin #stdout 0s 19536KB
comments (?)
stdin
copy 
5 3
stdout
copy 
2
https://ideone.com/cUMY7U
language:
C++14 (clang 8.0)
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!