Mock CCC '21 S3 - Lexicographically Smallest Permutation Subsequence

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 0.1s
Java 0.25s
Python 3 0.5s
Memory limit: 1G

Problem type

Given a list of N positive integers, none larger than K, compute the lexicographically smallest permutation of the first K positive integers that is a subsequence of the list.

Constraints

1 \le K \le N \le 2 \cdot 10^5

Each integer from 1 to K appears at least once in the list.

Input Specification

The first line contains two space-separated integers N and K. Each of the next N lines contains a single integer, the integers of the list in order.

Output Specification

Output K space-separated integers, the lexicographically smallest permutation that is a subsequence.

Sample Input

6 3
3
2
1
3
1
3

Sample Output

2 1 3

Comments


  • 0
    maxcruickshanks  commented on Jan. 1, 2024, 6:37 p.m.

    Since the original data were weak, an additional test case was added, and all submissions were rejudged.


  • 2
    zhenga1  commented on Feb. 15, 2021, 7:45 a.m.

    Can I ask why I am getting presentation error?


    • 2
      Aaeria  commented on Feb. 16, 2021, 4:24 p.m.

      you have to remove trailing spaces and end with a newline