요세푸스 문제 2

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

"""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()