Submission #1814914
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<<21]; int g[1<<21]; int l[30][200010]; int r[30][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)&&(r[1][f[i]+1]>=n||g[(all-1)^i^1]<=r[1][f[i]+1]+1)) b[l[1][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]-1)) printf("Possible\n"); else printf("Impossible\n"); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Camel and Oases |
User | yww |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2216 Byte |
Status | AC |
Exec Time | 122 ms |
Memory | 50176 KB |
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
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All | 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 | AC | 5 ms | 18560 KB |
00_example_02.txt | AC | 5 ms | 18560 KB |
00_example_03.txt | AC | 6 ms | 24704 KB |
01.txt | AC | 81 ms | 47232 KB |
02.txt | AC | 26 ms | 41088 KB |
03.txt | AC | 82 ms | 47232 KB |
04.txt | AC | 26 ms | 41088 KB |
05.txt | AC | 80 ms | 47232 KB |
06.txt | AC | 87 ms | 47744 KB |
07.txt | AC | 30 ms | 41344 KB |
08.txt | AC | 85 ms | 47616 KB |
09.txt | AC | 31 ms | 41472 KB |
10.txt | AC | 82 ms | 47360 KB |
11.txt | AC | 49 ms | 45568 KB |
12.txt | AC | 84 ms | 47488 KB |
13.txt | AC | 121 ms | 50176 KB |
14.txt | AC | 82 ms | 47232 KB |
15.txt | AC | 27 ms | 41088 KB |
16.txt | AC | 82 ms | 47232 KB |
17.txt | AC | 26 ms | 41088 KB |
18.txt | AC | 76 ms | 47232 KB |
19.txt | AC | 45 ms | 45184 KB |
20.txt | AC | 86 ms | 47616 KB |
21.txt | AC | 30 ms | 41344 KB |
22.txt | AC | 86 ms | 47616 KB |
23.txt | AC | 31 ms | 41472 KB |
24.txt | AC | 81 ms | 47360 KB |
25.txt | AC | 49 ms | 45568 KB |
26.txt | AC | 86 ms | 47616 KB |
27.txt | AC | 121 ms | 50176 KB |
28.txt | AC | 87 ms | 47616 KB |
29.txt | AC | 29 ms | 41344 KB |
30.txt | AC | 86 ms | 47616 KB |
31.txt | AC | 48 ms | 45440 KB |
32.txt | AC | 83 ms | 47488 KB |
33.txt | AC | 48 ms | 45440 KB |
34.txt | AC | 84 ms | 47488 KB |
35.txt | AC | 122 ms | 50176 KB |
36.txt | AC | 81 ms | 47232 KB |
37.txt | AC | 27 ms | 41088 KB |
38.txt | AC | 82 ms | 47232 KB |
39.txt | AC | 27 ms | 41088 KB |
40.txt | AC | 80 ms | 47232 KB |
41.txt | AC | 44 ms | 45184 KB |
42.txt | AC | 81 ms | 47232 KB |
43.txt | AC | 45 ms | 45184 KB |
44.txt | AC | 81 ms | 47232 KB |
45.txt | AC | 45 ms | 45184 KB |
46.txt | AC | 30 ms | 41344 KB |
47.txt | AC | 85 ms | 47488 KB |
48.txt | AC | 48 ms | 45440 KB |
49.txt | AC | 85 ms | 47488 KB |
50.txt | AC | 48 ms | 45440 KB |
51.txt | AC | 85 ms | 47488 KB |
52.txt | AC | 48 ms | 45440 KB |
53.txt | AC | 85 ms | 47488 KB |
54.txt | AC | 48 ms | 45440 KB |
55.txt | AC | 85 ms | 47488 KB |
56.txt | AC | 29 ms | 41344 KB |
57.txt | AC | 85 ms | 47488 KB |
58.txt | AC | 49 ms | 45440 KB |
59.txt | AC | 84 ms | 47488 KB |
60.txt | AC | 49 ms | 45440 KB |
61.txt | AC | 85 ms | 47488 KB |
62.txt | AC | 49 ms | 45440 KB |
63.txt | AC | 85 ms | 47488 KB |
64.txt | AC | 48 ms | 45440 KB |
65.txt | AC | 86 ms | 47488 KB |
66.txt | AC | 5 ms | 18560 KB |
67.txt | AC | 5 ms | 18560 KB |