Description

对于一个给定的 \(S = \{a_1, a_2, a_3, \ldots, a_n\}\), 若有\(P = \{a_{x_1}, a_{x_2}, a_{x_3}, \ldots, a_{x_m}\}\) 满足 \(x_1 \lt x_2 \lt \ldots \lt x_m\) 且 \(a_{x_1} \lt a_{x_2} \lt \ldots \lt a_{x_m}\), 那么就称 \(P\) 为 \(S\) 的一个上升序列. 如果有多个 \(P\) 满足条件, 那么我们想求字典序最小的那个. 任务给出 \(S\) 序列, 给出若干询问. 对于第 \(i\) 个询问, 求出长度为 \(L_i\) 的上升序列, 如有多个, 求出字典序最小的那个 (即首先 \(x_1\) 最小, 如果不唯一, 再看 \(x_2\) 最小...... ) , 如果不存在长度为 \(L_i\) 的上升序列, 则打印 Impossible.

Input

第一行一个 \(n\), 表示序列一共有 \(n\) 个元素

第二行 \(n\) 个数, 为 \(a_1, a_2, \ldots, a_n\)

第三行一个 \(m\), 表示询问次数.

下面接 \(m\) 行每行一个数 \(L\), 表示要询问长度为 \(L\) 的上升序列.

Output

对于每个询问, 如果对应的序列存在, 则输出, 否则打印 Impossible.

Sample Input

6
3 4 1 2 3 6
3
6
4
5

Sample Output

Impossible
1 2 3 6
Impossible

Data Range

对于所有的数据, 满足:\(n \leq 10000, m \leq 1000\)

Explanation

先借鉴一下黄学长的题解:

首先求出以每个数为开头上升序列长度, 即倒着做最长下降子序列

然后, 把字典序尽量小的放前面

即若要求的序列长度为 \(x\), 如果以第一个数 (字典序最小的数) 开头的最长上升子 序列大于等于 \(x\), 则将它放在答案第一个, 第二个数开头小于 \(x\), 则舍弃, 第三个大于 \(x - 1\), 放答案第二个, 以此类推

简单地说, 就是先处理出来一个固定长度的子序列, 其第一项最大可以是多少; 从一个固定位置开始的子序列, 其长度最长是多少. 这个操作, 如果用二分搜索优化的话, 其时间复杂度是 \(O(n \log n)\), 不然则是 \(O(n^2)\).

然后在询问的时候, 就每一次选取最小的那个值往下查就可以了, 然后总时间复杂度应该是一个稳定的 \(O(n \log n + n \cdot m)\).

应该可以凑合过掉这道题.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 100100;

int n, m, max_len;
int arr[maxn],
    len[maxn], // Maximum length of subsequence, counting from right
    best[maxn]; // Largest value that initiates a i-subsequence

int search_max_len_lt(int v)
{
    int l = 1, r = max_len, res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (best[mid] > v)
            res = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    return res;
}

void eval(int v)
{
    int last_val = 0;
    for (int i = 1; i <= n; i++)
        if (len[i] >= v && arr[i] > last_val) {
            printf("%d", arr[i]);
            if (v > 1) // Prevent line-end spaces
                printf(" ");
            last_val = arr[i];
            v--; if (v <= 0) break; // Termination
        }
    printf("\n");
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Pre-processing available lengths
    for (int i = n; i >= 1; i--) {
        int prev_len = search_max_len_lt(arr[i]);
        len[i] = prev_len + 1;
        max_len = max(max_len, prev_len + 1);
        if (arr[i] > best[prev_len + 1])
            best[prev_len + 1] = arr[i];
    }
    // Answering queries
    scanf("%d", &m);
    for (int i = 1, x; i <= m; i++) {
        scanf("%d", &x);
        if (x <= max_len)
            eval(x);
        else
            printf("Impossible\n");
    }
    return 0;
}