BOJ)1168 조세퍼스 문제2

문제: icpc.me/1168

N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다.

세그먼트 트리를 이용하여 현재 위치에서 M번째 사람을 찾아내서 풀면 된다. 이때 주의 할 점은 환형이기 때문에 남아있는 사람수를 고려하여 모듈러 연산이 필요하다.  

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int seg[400040];
int n, m;
vector<int> ans;
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int val, int node, int x, int y) {
    if (x == y)
        return x;
    if (seg[node * 2] >= val)
        return query(val, node * 2, x, (x + y) / 2);
    else
        return query(val - seg[node * 2], node * 2 + 1, (x + y) / 2 + 1, y);
}
int squery(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return squery(lo, hi, node * 2, x, mid) + squery(lo, hi, node * 2 + 1, mid + 1, y);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        update(i, 1, 1, 1, n);
    int mod = n - 1;
    ans.push_back(m);
    update(m, 0, 1, 1, n);
    for (int i = 2; i <= n; i++) {
        int x = (squery(1, ans.back(), 1, 1, n) + m) % mod;
        if (!x)x = mod;
        ans.push_back(query(x, 1, 1, n));
        update(ans.back(), 0, 1, 1, n);
        mod--;
    }
    printf("<");
    for (int i = 0; i < ans.size(); i++) {
        if (i == ans.size() - 1)
            printf("%d>\n", ans[i]);
        else
            printf("%d, ", ans[i]);
    }
    return 0;
}