Submission #4265680


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=2e5+10,inf=0x3f3f3f3f;
int tmp,Max[20][maxn],Min[20][maxn],a[maxn],f[1<<20],g[1<<20],R[maxn];
int main(){
	int n=read(),V=read();
	REP(i,1,n) a[i]=read();
	tmp=-1;
	memset(Min,inf,sizeof(Min));
	while(1){
		++tmp;
		int lst=1;
		REP(i,2,n) if(a[i]-a[i-1]>V){
			chkmax(Max[tmp][lst],i-1);
			chkmin(Min[tmp][i-1],lst);
			lst=i;
		}
		chkmax(Max[tmp][lst],n);
		chkmin(Min[tmp][n],lst);
		REP(i,1,n) chkmax(Max[tmp][i],Max[tmp][i-1]);
		Max[tmp][n+1]=n;
		DREP(i,n,1) chkmin(Min[tmp][i],Min[tmp][i+1]);
		Min[tmp][0]=1;
		if(V==0) break;
		V/=2;
	}
	memset(g,inf,sizeof(g));
	f[0]=0,g[0]=n+1;
	REP(i,0,(1<<tmp)-1)
		REP(j,1,tmp) if((i&(1<<(j-1)))==0){
			chkmax(f[i|(1<<(j-1))],Max[j][f[i]+1]);
			chkmin(g[i|(1<<(j-1))],Min[j][g[i]-1]);
		}
	memset(R,inf,sizeof(R));
	REP(i,0,(1<<tmp)-1){
		if(f[i]>=g[i^iend]-1){
			REP(j,1,n) printf("Possible\n");
			return 0;
		}
		chkmin(R[f[i]+1],g[i^iend]-1);
	}
	DREP(i,n,1) chkmin(R[i],R[i+1]);
	REP(i,1,n) printf("%s\n",(R[Min[0][i]]<=Max[0][i])?"Possible":"Impossible");
	return 0;
}

Submission Info

Submission Time
Task E - Camel and Oases
User zhou888
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1892 Byte
Status
Exec Time 67 ms
Memory 41344 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 1000 / 1000 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt
Case Name Status Exec Time Memory
00_example_01.txt 8 ms 26880 KB
00_example_02.txt 7 ms 26880 KB
00_example_03.txt 8 ms 28928 KB
01.txt 30 ms 39168 KB
02.txt 14 ms 37120 KB
03.txt 30 ms 39168 KB
04.txt 14 ms 37120 KB
05.txt 30 ms 39168 KB
06.txt 35 ms 39424 KB
07.txt 17 ms 37248 KB
08.txt 33 ms 39296 KB
09.txt 18 ms 37376 KB
10.txt 31 ms 39296 KB
11.txt 23 ms 37376 KB
12.txt 32 ms 39296 KB
13.txt 66 ms 41344 KB
14.txt 30 ms 39168 KB
15.txt 14 ms 37120 KB
16.txt 30 ms 39168 KB
17.txt 14 ms 37120 KB
18.txt 29 ms 39168 KB
19.txt 19 ms 37120 KB
20.txt 34 ms 39424 KB
21.txt 17 ms 37248 KB
22.txt 34 ms 39424 KB
23.txt 19 ms 37376 KB
24.txt 32 ms 39296 KB
25.txt 23 ms 37376 KB
26.txt 34 ms 39424 KB
27.txt 66 ms 41344 KB
28.txt 35 ms 39424 KB
29.txt 17 ms 37248 KB
30.txt 34 ms 39424 KB
31.txt 22 ms 37248 KB
32.txt 32 ms 39296 KB
33.txt 22 ms 37248 KB
34.txt 33 ms 39296 KB
35.txt 67 ms 41344 KB
36.txt 30 ms 39168 KB
37.txt 14 ms 37120 KB
38.txt 30 ms 39168 KB
39.txt 14 ms 37120 KB
40.txt 29 ms 39168 KB
41.txt 19 ms 37120 KB
42.txt 30 ms 39168 KB
43.txt 19 ms 37120 KB
44.txt 29 ms 39168 KB
45.txt 19 ms 37120 KB
46.txt 16 ms 37248 KB
47.txt 33 ms 39296 KB
48.txt 22 ms 37248 KB
49.txt 33 ms 39296 KB
50.txt 21 ms 37248 KB
51.txt 32 ms 39296 KB
52.txt 21 ms 37248 KB
53.txt 32 ms 39296 KB
54.txt 21 ms 37248 KB
55.txt 33 ms 39296 KB
56.txt 17 ms 37248 KB
57.txt 33 ms 39296 KB
58.txt 23 ms 37248 KB
59.txt 32 ms 39296 KB
60.txt 22 ms 37248 KB
61.txt 33 ms 39296 KB
62.txt 22 ms 37248 KB
63.txt 33 ms 39296 KB
64.txt 22 ms 37248 KB
65.txt 33 ms 39296 KB
66.txt 7 ms 26880 KB
67.txt 8 ms 26880 KB