bzoj#P1136. [POI2009]Arc

[POI2009]Arc

题目描述

给定一个序列 aia_i 和一个整数 kk ,求出 aa 的一个长度为 kk 的子序列 abia_{bi} 满足:

  1. 1b1b2bk1 \le b_1 \le b_2 \le \dots \le b_k
  2. 在满足 (1) 的情况下 {ab1,ab2,,abk}\{a_{b_1}, a_{b_2}, \dots , a_{b_k}\} 字典序最大。

输入格式

第一行一个数 kk,以下一行,为序列 aia_i。以一个单独的 00 结束。

输出格式

kk 行,每行一个数,其中第 ii 行为 abia_{b_i}

12
5 8 3 15 8 0
12
15
8

数据规模与约定

$1 \le a_i \le 10^9,k \le n \le 1.5 \times 10^7,k \le 10^6$.

提示

按照这里: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。