boj1168.cpp

#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define MAXN 100100
 
int IndexTree[4 * MAXN];
int N, M;
 
int p = 1;
 
int num = 1;
 
int Cal_Index(int N){
    num += M - 1;
    num %= N;
 
    if (num == 0) return num = N;
    else return num;
}
 
void Init_IndexTree(void){
    //인덱스 트리 초기화 구성
    while (N > p) p <<= 1;
 
    for (int i = 0; i < N; i++)
        IndexTree[i + p] = 1;
 
    for (int i = p - 1; i >= 1; i--){
        IndexTree[i] += IndexTree[i * 2] + IndexTree[i * 2 + 1];
    }
}
 
void update(int index){
    IndexTree[index + p] = 0;
 
    for (int i = (index + p)/2 ; i >= 1; i >>= 1)
        IndexTree[i] = IndexTree[i * 2] + IndexTree[i * 2 + 1];
}
 
int search(int k){
    int index = 1;
 
    while ( index < p ){
        if (IndexTree[index * 2] >= k){
            index *= 2;
        }
        else{
            k -= IndexTree[index * 2];
            index = index * 2 + 1;
        }
    }
 
    return index-p;
}
 
int main(){
    cin >> N >> M;
 
    Init_IndexTree();
 
    cout << "<";
    for (int i = 0; i < N; i++){
        int target = search(Cal_Index(N - i));
        printf("%d", target + 1);
        if (i != N - 1)
            printf(", ");
        update(target);
    }
    cout << ">";
    return 0;
}