Submission #1315951
Source Code Expand
#include <bits/stdc++.h> #define int long long #define P(x) cout << x << endl #define D(x) P(#x << ": " << x) #define F(i,n) for (int i=0; i<(int)(n); i++) #define DEC(i,n) for (int i=(int)(n); --i>=0;) #define pb push_back #define all(v) v.begin(), v.end() using namespace std; void MI(int &a, int v) {a = min(a,v);} void MA(int &a, int v) {a = max(a,v);} const int N=2e5, L=18, PL=1<<L; int l,n,v,pl; deque<int> len; void gen(int x[], int nxt[][N], int reach[]) { F(k,l) { int cur=0; F(i,n+1) { if (i == n || (i-1 >= 0 && abs(x[i] - x[i-1]) > len[k])) { while (cur < i) { nxt[k][cur] = i; cur++; } } } } F(mask,pl) { reach[mask] = 0; F(k,l) if (mask & 1<<k) MA(reach[mask], nxt[k][reach[mask-(1<<k)]]); } } void print(int nxt[][N]) { F(k,l) { cout<<len[k]<<": "; F(i,n) cout<<nxt[k][i]<<" \n"[i==n-1]; } } int x[N], rev[N]; int nxt[L][N], pre[L][N], rLeft[PL], rRight[PL]; bool ok[N]; signed main() { cin>>n>>v; F(i,n) cin>>x[i], rev[n-1-i] = x[i], ok[i] = false; len = {v}; int cur = v; while (cur) cur/=2, len.push_front(cur); l = len.size(); pl = 1<<l; gen(x, nxt, rLeft); gen(rev, pre, rRight); //P("nxt:"); print(nxt); //P("pre:"); print(pre); //F(k,pl) cout<<bitset<3>(k)<<":"<<rLeft[k]<<" \n"[k==pl-1]; int start = pl/2; int offer[n+1]; // if you finish at >= i, we can accept a start <= offer[i] F(i,n+1) offer[i] = -1; F(mleft,start) { int le = rLeft[mleft], ri = n - rRight[start-1-mleft]; //P(le<<" "<<ri); MA(offer[ri], le); } int best = -1; cur = 0; while (cur < n) { int lim = nxt[l-1][cur]; for (int i=cur; i<=lim; i++) MA(best, offer[i]); for (int i=cur; i<lim; i++) P((cur <= best ? "Possible" : "Impossible")); cur = lim; } }
Submission Info
Submission Time | |
---|---|
Task | E - Camel and Oases |
User | vlecomte |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2079 Byte |
Status | WA |
Exec Time | 485 ms |
Memory | 67200 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 4 ms | 16640 KB |
00_example_02.txt | AC | 4 ms | 16640 KB |
00_example_03.txt | AC | 6 ms | 24832 KB |
01.txt | WA | 85 ms | 63488 KB |
02.txt | AC | 30 ms | 62720 KB |
03.txt | WA | 85 ms | 63488 KB |
04.txt | AC | 31 ms | 62720 KB |
05.txt | WA | 85 ms | 63488 KB |
06.txt | WA | 144 ms | 64000 KB |
07.txt | AC | 66 ms | 63104 KB |
08.txt | WA | 122 ms | 63872 KB |
09.txt | AC | 73 ms | 63104 KB |
10.txt | WA | 103 ms | 63744 KB |
11.txt | AC | 93 ms | 64000 KB |
12.txt | WA | 108 ms | 63744 KB |
13.txt | WA | 475 ms | 67200 KB |
14.txt | WA | 84 ms | 63488 KB |
15.txt | AC | 30 ms | 62720 KB |
16.txt | WA | 84 ms | 63488 KB |
17.txt | AC | 30 ms | 62720 KB |
18.txt | AC | 84 ms | 63488 KB |
19.txt | AC | 48 ms | 63488 KB |
20.txt | WA | 136 ms | 64000 KB |
21.txt | AC | 68 ms | 63104 KB |
22.txt | WA | 129 ms | 63872 KB |
23.txt | AC | 80 ms | 63232 KB |
24.txt | AC | 109 ms | 63744 KB |
25.txt | AC | 89 ms | 63872 KB |
26.txt | WA | 129 ms | 63872 KB |
27.txt | WA | 478 ms | 67200 KB |
28.txt | WA | 135 ms | 64000 KB |
29.txt | AC | 64 ms | 63104 KB |
30.txt | WA | 133 ms | 64000 KB |
31.txt | AC | 80 ms | 63872 KB |
32.txt | WA | 108 ms | 63744 KB |
33.txt | AC | 86 ms | 63872 KB |
34.txt | WA | 121 ms | 63872 KB |
35.txt | WA | 485 ms | 67200 KB |
36.txt | WA | 85 ms | 63488 KB |
37.txt | AC | 30 ms | 62720 KB |
38.txt | WA | 84 ms | 63488 KB |
39.txt | AC | 30 ms | 62720 KB |
40.txt | AC | 85 ms | 63488 KB |
41.txt | AC | 48 ms | 63488 KB |
42.txt | AC | 84 ms | 63488 KB |
43.txt | AC | 48 ms | 63488 KB |
44.txt | WA | 84 ms | 63488 KB |
45.txt | AC | 48 ms | 63488 KB |
46.txt | AC | 62 ms | 62976 KB |
47.txt | WA | 118 ms | 63872 KB |
48.txt | AC | 80 ms | 63872 KB |
49.txt | WA | 118 ms | 63872 KB |
50.txt | AC | 76 ms | 63744 KB |
51.txt | WA | 112 ms | 63744 KB |
52.txt | AC | 76 ms | 63744 KB |
53.txt | WA | 115 ms | 63744 KB |
54.txt | AC | 77 ms | 63744 KB |
55.txt | WA | 120 ms | 63872 KB |
56.txt | AC | 55 ms | 62976 KB |
57.txt | AC | 119 ms | 63872 KB |
58.txt | AC | 81 ms | 63872 KB |
59.txt | WA | 107 ms | 63744 KB |
60.txt | AC | 82 ms | 63872 KB |
61.txt | WA | 117 ms | 63872 KB |
62.txt | AC | 80 ms | 63872 KB |
63.txt | WA | 117 ms | 63872 KB |
64.txt | AC | 82 ms | 63872 KB |
65.txt | WA | 119 ms | 63872 KB |
66.txt | AC | 4 ms | 16640 KB |
67.txt | AC | 4 ms | 16640 KB |