Railway Transportation

• Passport Control과 동일한 수열을 최소 개수의 증가 부분 수열로 나누기 문제인데, 역추적이 붙어있는 형태이다
• 각 원소들이 어떤 큐에 들어가는지를 추적하는 것도, 위 링크에서 설명했듯이 이분탐색으로 LDS를 구하는 알고리즘을 활용해서 처리 가능하다. 이것을 구하고 나면, pop연산이 발생하는 큐들의 번호 순서를 출력하는 것은, 그냥 원소들을 정렬한 뒤에 각 원소가 들어가있는 큐의 번호를 순서대로 써주면 된다.

"""Solution code for "BOJ 6656. Railway Transportation".

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

Tags: [LIS]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.run_until_all_zero
def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    nums = [int(x) for x in sys.stdin.readline().split()]

    lengths = seqtask.longest_dec_subseq_length_by_last_elem(nums, strict=True)
    if max(lengths) > M:
        print('Transportation failed')
    else:
        print(*lengths)
        print(*(lengths[i] for i in sorted(range(N), key=nums.__getitem__)))


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_dec_subseq_length_by_last_elem