比赛 |
假期找点事儿做题吧 |
评测结果 |
AAAAAAAAAA |
题目名称 |
上升序列 |
最终得分 |
100 |
用户昵称 |
CSU_Turkey |
运行时间 |
1.083 s |
代码语言 |
C++ |
内存使用 |
0.47 MiB |
提交时间 |
2017-06-09 20:44:50 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10008],b[10008],g[10008],h[10008],mid,book;
inline int erfen(int x,int y,int z)
{
while(x<y)
{
int mid=(x+y)/2;
if(b[mid]<=z)y=mid;
else x=mid+1;
}
return x;
}
int main()
{
// freopen("1.txt","r",stdin);
freopen("lis.in","r",stdin);
// freopen("b.out","w",stdout);
freopen("lis.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
memset(b,0x7f,sizeof(b));
int len=1;
for(int i=n;i>=1;i--)//这里一定要是倒着枚举,因为为了满足字典序,最后输出时需要从左往右来看
//如果正枚举,得到的g数组无法看到后面是否有数字能满足以当前序列走可以满足题意
{
int u=b[len-1];
if(a[i]<u)
b[len++]=a[i],
g[i]=len-1;
else
{
int ghb=erfen(1,len-1,a[i]);
b[ghb]=a[i],
g[i]=ghb;
}
/*if(len==x+1)
{
book=1;
break;
}*/
}
/*if(book==1)
for(int i=len-1;i>=1;i--)
cout<<b[i];
else cout<<"Impossible";*/
for(int j=1;j<=m;j++)
{
int x;
scanf("%d",&x);
// if(j!=206)continue;
memset(h,0,sizeof(h));
if(len-1<x)
{
cout<<"Impossible";
}
else
{
// for(int i=1;i<=n;i++)
// cout<<g[i]<<" ";
int last=-100;
int jj=1;
for(int i=1;x;i++)
{
if(g[i]>=x&&a[i]>last)
{
last=a[i];
x--;
h[jj++]=a[i];
}//cout<<i<<" ";
}
for(int i=1;i<jj;i++)
cout<<h[i]<<" ";
}
}
return 0;
}