[POI2009]Arc
时间限制：50s 【提交】 空间限制：162MB
题目描述
给定一个序列{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]} 字典序最大。
输入格式
第一行一个数k，以下一行，为序列ai。以一个单独的0结束
输出格式
k行，每行一个数，其中第i行为a[bi]。
样例输入
12 5 8 3 15 8 0
样例输出
12 15 8
提示
按照这里：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
题目来源
没有写明来源