Josephus Problem II.cpp

#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFL 9223372036854775807
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define ull unsigned long long
#define M 1000'000'007
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define take(x) scanf("%d",&x)
#define DE(x) printf("\ndebug %d\n",x);
#define vout(x) for(int i=0;i<x.size();i++) printf("%d ",x[i]);
#define pie acos(-1)
#define MOD 998244353

/**
    OST using BIT
    1- indexed
    order_of_key(x):    find the the number of entries lower than or equal to x
    find_by_order(k):   find the kth smallest number
    find(x):            find if a number is present in set
    erase(x):           delete a entry
    insert(x):          enter a entry
*/

class OST{
    int MAX_VAL = 1429450;
    vector<int> BIT;
    void update(int i, int add){
        while (i > 0 && i < BIT.size()){
            BIT[i] += add;
            i = i + (i & (-i));
        }
    }

    int sum(int i){
        int ans = 0;
        while (i > 0){
            ans += BIT[i];
            i = i - (i & (-i));
        }
        return ans;
    }
public:
    OST(int val){
        MAX_VAL = val;
        BIT.resize(MAX_VAL);
    }
    int find_by_order(int k){
        int l = 0;
        int h = BIT.size();
        while (l < h){
            int mid = (l + h) / 2;
            if (k <= sum(mid))
                h = mid;
            else
                l = mid+1;
        }
        return l;
    }

    void insert(int x){
        if( /*find(x) or*/ x<=0 or x>=BIT.size() ) return;
        update(x, 1);
    }

    void erase(int x){
        if( !find(x) ) return;
        update(x, -1);
    }


    int order_of_key(int x){
        if( x<=0 ) return 0;
        if( x>BIT.size() ) return sum( BIT.size()-1 );
        return sum(x);
    }
    bool find(int x){
        if( x<=0 or x>=BIT.size() ) return false;
        return sum(x)-sum(x-1)>0 ;
    }
    int size(){
        return sum( BIT.size()-1 );
    }

};
int main(){

    int n,K;
    cin>>n>>K;

    OST s(n+1);
    for(int i=1;i<=n;i++) s.insert(i);

    int curr = 1;
    for(int i=0;i<n;i++){
        int rem = n-i;
        int k = (curr+K-1)%rem + 1;
        int val = s.find_by_order(k);
        s.erase(val);
        cout<<val<<" ";
        curr = k;
    }

}