====== 요세푸스 문제 2 ======

===== 풀이 =====
  * [[ps:problems:boj:1158]] 에서 n의 크기 제한을 늘린 문제. [[ps:problems:boj:1158]]은 O(n^2) 솔루션으로도 통과 가능했지만, 이 문제는 O(nlogn) 으로 풀어야 한다. 풀이는 [[ps:problems:boj:1158]] 참고.
  * 하지만 이 문제는 n의 크기제한이 늘어난 것 외에도, 제한시간이 언어별로 따로 정해져있고, python기준으로 상당히 타이트하다. python과 pypy이 동일하게 750ms의 제한시간을 갖고 있는데, [[ps:problems:boj:1158]] 의 O(nlogn) 코드를 그대로 복붙해서 제출할 경우 python은 시간초과, pypy는 약 250ms정도에 통과된다.
  * Python에서 통과시키기 위해서는 동일한 알고리즘에서 열심히 상수 최적화를 하는 과정이 필요했다.[[:ps:teflib:segmenttree#OrderStatisticTree|teflib.segmenttree.OrderStatisticTree]]를 사용해서 kth와 add함수를 호출하던 방법 대신에, k번째 수를 찾으면서 바로 delete 시키는 함수를 새로 만들었고, 클래스를 사용하는 대신 그냥 메인함수 안에 로직을 옮겨오는 방식으로 쥐어짜서 최적화를 하고서야 python3으로도 통과시킬수 있었다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1168. 요세푸스 문제 2".

- Problem link: https://www.acmicpc.net/problem/1168
- Solution link: http://www.teferi.net/ps/problems/boj/1168
"""


def main():
    def delete_kth(k: int):
        i = 1
        while i < tree_size:
            i += i
            t = tree[i]
            if t < k:
                k -= t
                i += 1
            tree[i] -= 1
        tree[1] -= 1
        return i - tree_size

    N, K = [int(x) for x in input().split()]

    tree_size = 1 << (N - 1).bit_length()
    tree = [0] * (tree_size + tree_size)
    tree[tree_size:tree_size + N] = [1] * N
    for i in range(tree_size - 1, 0, -1):
        tree[i] = tree[i + i] + tree[i + i + 1]
        
    order = 0
    answer = []
    for i in range(N, 0, -1):
        order = (order + K - 1) % i
        num = delete_kth(order + 1)
        answer.append(num + 1)

    print('<', end='')
    print(', '.join(str(x) for x in answer), end='>')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_4}}