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
AC × 3
AC × 39
WA × 31
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