14191: 【原4191】上升序列进阶

题目描述

author: LH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4191

Description

对于一个给定的S={a1,a2,a3,…,an},若有P={\(a_{x1}\),\(a_{x2}\),\(a_{x3}\),…,\(a_{xm}\)},满足(x1 < x2 < … < xm)且（\(a_{x1}\) < \(a_{x2}\) < … < \(a_{xm}\))。
那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。
任务给出S序列，给出若干询问。
对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……）
如果不存在长度为Li的上升序列，则打印Impossible.

Input Format

第一行一个N，表示序列一共有N个元素
第二行N个数，为a1,a2,…,an
第三行一个M，表示询问次数。
下面接M行每行一个数L，表示要询问长度为L的上升序列。

Output Format

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

Sample1 Input

6
3 4 1 2 3 6
3
6
4
5

Sample1 Output

Impossible
1 2 3 6
Impossible

数据规模

对于30%的数据，\(1 \leq N \leq 100,1 \leq M \leq 10\)
对于50%的数据，\(1 \leq N \leq 10000,1 \leq M \leq 10\)
对于70%的数据，\(1 \leq N \leq 1000,1 \leq M \leq 1000\)
对于100%的数据，\(1 \leq N \leq 10000,1 \leq M \leq 1000\)

zqy2018's solution

/*
    See the original problem at https://www.luogu.com.cn/problem/P2215
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[10005];
int b[10005], ans[10005] = {0};
int f[10005];
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    fill(b, b + n + 1, INT_MAX);
}
void solve(){
    int ans = 0;
    for (int i = n; i >= 1; --i){
        int t = lower_bound(b, b + n + 1, -a[i]) - b;
        f[i] = t + 1, b[t] = -a[i];
        ans = max(ans, f[i]);
    }
    int q = read();
    while (q--){
        int t = read();
        if (t > ans){
            printf("Impossible\n");
            continue;
        }
        int lst = INT_MIN;
        for (int i = 1; i <= n; ++i){
            if (f[i] >= t && a[i] > lst){
                printf("%d", a[i]);
                lst = a[i], --t;
                if (!t){
                    printf("\n");
                    break;
                }else printf(" ");
            }
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}