Hide
Longest Increasing Subsequence
Input
The input consists of several test cases. Each test case begins with a positive integer $n \le 100\, 000$, indicating the length of a sequence. Then follows a sequence of $n$ integers, that fit into 32-bit integer variables.
Output
For each test case, output a line containing the length of a longest increasing subsequence, followed by a line containing the indices of the elements in one such sequence (the first element has index $0$, the second index $1$, and so on). The indices should be given in ascending order.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 1 2 3 4 5 6 7 8 9 10 10 1 1 1 1 1 1 1 1 1 1 10 5 19 5 81 50 28 29 1 83 23 |
10 0 1 2 3 4 5 6 7 8 9 1 7 5 0 1 5 6 8 |
CPU Time limit
2 seconds
Memory limit
1024 MB
Difficulty
6hard
Statistics
Show
Downloads
Author
Source
KTH CSC Popup 2006
License
