Submission #1814851

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
	if(a>b)
		swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
	char str[100];
	sprintf(str,"%s.in",s);
	freopen(str,"r",stdin);
	sprintf(str,"%s.out",s);
	freopen(str,"w",stdout);
#endif
}
int rd()
{
	int s=0,c;
	while((c=getchar())<'0'||c>'9');
	do
	{
		s=s*10+c-'0';
	}
	while((c=getchar())>='0'&&c<='9');
	return s;
}
int upmin(int &a,int b)
{
	if(b<a)
	{
		a=b;
		return 1;
	}
	return 0;
}
int upmax(int &a,int b)
{
	if(b>a)
	{
		a=b;
		return 1;
	}
	return 0;
}
int v[200010];
int f[1<<20];
int g[1<<20];
int l[20][200010];
int r[20][200020];
int a[200010];
int b[200010];
int main()
{
//	open("agc012e");
	int n;
	scanf("%d%d",&n,&v[1]);
	int i,j;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int t=1;
	while(1)
	{
		v[t+1]=v[t]/2;
		t++;
		if(!v[t])
			break;
	}
	for(i=1;i<=t;i++)
	{
		for(j=1;j<=n;j++)
			if(j==1||a[j]-a[j-1]>v[i])
				l[i][j]=j;
			else
				l[i][j]=l[i][j-1];
		for(j=n;j>=1;j--)
			if(j==n||a[j+1]-a[j]>v[i])
				r[i][j]=j;
			else
				r[i][j]=r[i][j+1];
	}
	memset(f,0,sizeof f);
	int all=1<<t;
	for(i=0;i<all;i++)
		for(j=1;j<=t;j++)
			if(!((i>>(j-1))&1))
			{
				if(f[i]==n)
					upmax(f[i|(1<<(j-1))],f[i]);
				else
					upmax(f[i|(1<<(j-1))],r[j][f[i]+1]);
			}
	for(i=0;i<all;i++)
		g[i]=n+1;
	for(i=0;i<all;i++)
		for(j=1;j<=t;j++)
			if(!((i>>(j-1))&1))
			{
				if(g[i]==1)
					upmin(g[i|(1<<(j-1))],g[i]);
				else
					upmin(g[i|(1<<(j-1))],l[j][g[i]-1]);
			}
	if(f[all-2]>=n)
	{
		for(i=1;i<=n;i++)
			printf("Possible\n");
		return 0;
	}
	for(i=0;i<all;i++)
		if(!(i&1)&&(f[i]+r[1][f[i]+1]>=n||g[(all-1)^i^1]<=f[i]+r[1][f[i]+1]))
			b[f[i]+1]=1;
	int last=0;
	for(i=1;i<=n;i++)
	{
		if(b[i])
			last=i;
		if(l[1][i]<=last||(i<=r[1][1]&&r[1][1]>g[all-2]))
			printf("Possible\n");
		else
			printf("Impossible\n");
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void open(const char*)’:
./Main.cpp:24:24: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen(str,"r",stdin);
                        ^
./Main.cpp:26:25: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  freopen(str,"w",stdout);
                         ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:69:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&v[1]);
                        ^
./Main.cpp:72:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

Judge Result