「NOIP模拟赛by wulala」公主的工作
和bzoj1046并没多大差别吧。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt; int a[100005],f[100005],best[100005]; struct data{int v,p;}b[100005]; inline bool operator<(data a,data b) { return a.v<b.v; } void solve(int x) { int last=0; for(int i=1;i<=n;i++) if(f[b[i].p]>=x&&b[i].p>last) { printf("%d",b[i].v); if(x!=1)printf(" "); last=b[i].p; x--; if(!x)break; } printf("\n"); } int find(int x) { int l=1,r=cnt,ans=0; while(l<=r) { int mid=(l+r)>>1; if(best[mid]>x)ans=mid,l=mid+1; else r=mid-1; } return ans; } void pre() { for(int i=n;i;i--) { int t=find(a[i]); f[i]=t+1; cnt=max(cnt,t+1); if(best[t+1]<a[i]) best[t+1]=a[i]; } } int main() { //freopen("work.in","r",stdin); //freopen("work.out","w",stdout); n=read(); for(int i=1;i<=n;i++) b[i].v=a[i]=read(),b[i].p=i; sort(b+1,b+n+1); pre(); m=read(); for(int i=1;i<=m;i++) { int x=read(); if(x<=cnt)solve(x); else puts("Impossible"); } return 0; } |
Subscribe
计数器 9787271
OI 课件=>
OI 课件=>