UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1136. [POI2009]Arc

统计 下载数据

Description

给定一个序列{ai | 1 <= ai <= 1000000000 且 1 <= i <= n 且 n <= 15000000}和一个整数 k (k <= n 且 k <= 1000000),求出a的一个长度为k的子序列{a[bi]}满足: (1) 1 <= b1 <= b2 <= ... <= bk (2) 在满足(1)的情况下 {a[b1], a[b2], ... , a[bk]} 字典序最大。

Input

第一行一个数k,以下一行,为序列ai。以一个单独的0结束

Output

k行,每行一个数,其中第i行为a[bi]。

Sample Input

12
5 8 3 15 8 0

Sample Output

12
15
8

Hint

按照这里:http://main.edu.pl/en/archive/oi/16/arc

来写交互式的程序,然后把这个东西:http://oi.edu.pl/static/attachment/20110704/oi16-etap2-arc.zip

解压后把etap2/arc/prog里的carclib.c的内容贴到自己的源码中的一大堆“include”之前。这样这个程序就从交互式程序变成普通的程序了,就可以AC了。

鸣谢vfleaking

Source