問題一覧 > 通常問題

No.1804 Intersection of LIS

レベル : / AI推定難易度 : 1775 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 61
作問者 : NatsubiSogan / テスター : nok0 penguinman
お気に入りにしたユーザー ProblemId : 7029 / 自分の提出
問題文最終更新日: 2021-11-17 20:14:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 326 (順位表) の他の問題:

Problem Statement

You are given a sequence $P=(P_1,P_2,\dots,P_N)$ that is a permutation of $(1,2,\dots,N)$. $P$ may have several possible LIS (longest increasing subsequences). Enumerate the elements that are contained in all of them.

Input

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
  • All input values are integers.
  • $1 \leq N \leq 3 \times 10^5$
  • $P$ is a permutation of $(1,2,\dots,N)$.

Output

First, on line $1$, print the number of elements contained in all LIS of $P$.

Then, on line $2$, print the elements contained in all LIS of $P$, separated by spaces, in ascending order of index. If the number of elements is $0$, print an empty line as line $2$.

Finally, print a newline.

Sample

Sample 1
Input
5
1 4 3 2 5
Output
2
1 5

There are $3$ possible LIS: $(A_1,A_2,A_5)=(1,4,5), \ (A_1,A_3,A_5)=(1,3,5), \ (A_1,A_4,A_5)=(1,2,5)$.

The elements contained in all of these are $A_1 = 1, A_5 = 5$, so print them.

Sample 2
Input
3
2 3 1
Output
2
2 3

The only LIS is $(A_1,A_2)=(2,3)$.

Sample 3
Input
6
4 5 6 1 2 3
Output
0

The number of elements contained in all LIS may be $0$. In such a case, do not forget to print an empty line as line $2$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。