Submission #1725194

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> par;
const int N=(1<<20)+5;
int n,v,tot,sum,x[N],vn[N],nxt[25][N],f[N][25],l[N],r[N],bel[N],ok[N];
int imp(){
	rep(i,1,n+1) puts("Impossible");
	return 0;
}
void upd(int &x,int y){x=max(x,y);}
int main(){
	scanf("%d%d",&n,&v);
	rep(i,1,n) scanf("%d",x+i);
	--n;
	rep(i,1,n) x[i]=x[i+1]-x[i];
	while (v){
		vn[++tot]=v;
		v>>=1;
	}
	sort(vn+1,vn+1+tot);
	rep(i,1,n) x[i]=lower_bound(vn+1,vn+tot+1,x[i])-vn;
	rep(i,1,tot){
		nxt[i][n+1]=n+1;
		per(j,n,1) if (x[j]<=i) nxt[i][j]=nxt[i][j+1]; else nxt[i][j]=j;
	}
	rep(i,1,n+1) nxt[0][i]=i;
	++tot;
	int tmp=0;
	while (tmp<n+1){
		++sum;
		l[sum]=tmp+1;
		tmp=nxt[tot-1][tmp+1];
		r[sum]=tmp;
		rep(i,l[sum],r[sum]) bel[i]=sum;
	}
	if (sum>tot+2) return imp();
	f[0][0]=0;
	int mx=1<<(tot-1);
	rep(i,0,(1<<tot)-1) rep(j,0,sum){
		if (((i&mx)!=0)^(j!=0)) continue;
		int nw=f[i][j]+1;
		if (nw>n){
			ok[j]=1;
			continue;
		}
		if (j==0) upd(f[i|mx][bel[nw]],nxt[tot-1][nw]);
		rep(k,0,tot-2) if ((i&1<<k)==0)
			upd(f[i|1<<k][j],nxt[k][nw]);
	}
	rep(i,1,n+1) puts(ok[bel[i]]?"Possible":"Impossible");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:20:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&v);
                     ^
./Main.cpp:21:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,1,n) scanf("%d",x+i);
                            ^

Judge Result