Submission #5175838


Source Code Expand

Copy
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,V;
int x[MAXN],d[30],tot,r[30][MAXN],l[30][MAXN];
int dp[2][(1 << 19) + 5];
void Solve() {
    read(N);read(V);
    for(int i = 1 ; i <= N ; ++i) read(x[i]);
    d[0] = V / 2;
    while(d[tot]) {
	++tot;
	d[tot] = d[tot - 1] / 2;
    }
    for(int j = 0 ; j <= tot ; ++j) {
	r[j][N] = N;r[j][N + 1] = N + 1;
	for(int i = N - 1 ; i >= 1 ; --i) {
	    r[j][i] = i;
	    if(x[i + 1] - x[i] <= d[j]) r[j][i] = r[j][i + 1];
	}
	l[j][1] = 1;
	for(int i = 2 ; i <= N ; ++i) {
	    l[j][i] = i;
	    if(x[i] - x[i - 1] <= d[j]) l[j][i] = l[j][i - 1];
	}
    }
    dp[0][0] = 0;dp[1][0] = N + 1;
    for(int S = 1 ; S < (1 << (tot + 1)) ; ++S) {
	dp[1][S] = N + 1;
	for(int j = 0 ; j <= tot ; ++j) {
	    if(S >> j & 1) {
		dp[0][S] = max(r[j][dp[0][S ^ (1 << j)] + 1],dp[0][S]);
		dp[1][S] = min(l[j][dp[1][S ^ (1 << j)] - 1],dp[1][S]);
	    }
	}
    }
    int cnt = 0;
    for(int i = 1 ; i <= N ; ++i) {
	int l = i,r = i;
	while(r < N && x[r + 1] - x[r] <= V) ++r;
	i = r;
	++cnt;
    }
    if(cnt - 1 > tot + 1) {
	for(int i = 1 ; i <= N ; ++i) {
	    puts("Impossible");
	}
	return;
    }
    for(int i = 1 ; i <= N ; ++i) {
	int l = i,r = i;
	while(r < N && x[r + 1] - x[r] <= V) ++r;
	int A = (1 << tot + 1) - 1;
	bool f = 0;
	for(int S = 0 ; S < (1 << tot + 1) ; ++S) {
	    if(dp[0][S] >= l - 1 && dp[1][A ^ S] <= r + 1) {f = 1;break;}
	}
	for(int i = l ; i <= r ; ++i) {
	    if(f) puts("Possible");
	    else puts("Impossible");
	}
	i = r;
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

Submission Info

Submission Time
Task E - Camel and Oases
User sigongzi
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2361 Byte
Status
Exec Time 67 ms
Memory 38784 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 3 ms 8448 KB
00_example_02.txt 3 ms 8448 KB
00_example_03.txt 4 ms 12544 KB
01.txt 33 ms 34048 KB
02.txt 13 ms 31232 KB
03.txt 31 ms 34048 KB
04.txt 13 ms 31232 KB
05.txt 29 ms 34048 KB
06.txt 38 ms 34304 KB
07.txt 15 ms 31360 KB
08.txt 34 ms 34304 KB
09.txt 16 ms 31488 KB
10.txt 31 ms 34176 KB
11.txt 23 ms 33792 KB
12.txt 32 ms 34176 KB
13.txt 64 ms 38784 KB
14.txt 33 ms 34048 KB
15.txt 13 ms 31232 KB
16.txt 32 ms 34048 KB
17.txt 12 ms 31232 KB
18.txt 28 ms 34048 KB
19.txt 20 ms 33536 KB
20.txt 36 ms 34304 KB
21.txt 15 ms 31360 KB
22.txt 35 ms 34304 KB
23.txt 16 ms 31488 KB
24.txt 30 ms 34176 KB
25.txt 22 ms 33792 KB
26.txt 34 ms 34304 KB
27.txt 65 ms 38784 KB
28.txt 37 ms 34304 KB
29.txt 16 ms 31360 KB
30.txt 36 ms 34304 KB
31.txt 21 ms 33664 KB
32.txt 34 ms 34176 KB
33.txt 22 ms 33664 KB
34.txt 35 ms 34176 KB
35.txt 67 ms 38784 KB
36.txt 32 ms 34048 KB
37.txt 13 ms 31232 KB
38.txt 32 ms 34048 KB
39.txt 13 ms 31232 KB
40.txt 28 ms 34048 KB
41.txt 20 ms 33536 KB
42.txt 29 ms 34048 KB
43.txt 20 ms 33536 KB
44.txt 32 ms 34048 KB
45.txt 18 ms 33536 KB
46.txt 15 ms 31360 KB
47.txt 36 ms 34176 KB
48.txt 22 ms 33664 KB
49.txt 32 ms 34176 KB
50.txt 22 ms 33664 KB
51.txt 35 ms 34176 KB
52.txt 22 ms 33664 KB
53.txt 35 ms 34176 KB
54.txt 22 ms 33664 KB
55.txt 35 ms 34176 KB
56.txt 14 ms 31360 KB
57.txt 31 ms 34176 KB
58.txt 22 ms 33664 KB
59.txt 31 ms 34176 KB
60.txt 22 ms 33664 KB
61.txt 35 ms 34176 KB
62.txt 22 ms 33664 KB
63.txt 36 ms 34176 KB
64.txt 22 ms 33664 KB
65.txt 35 ms 34176 KB
66.txt 3 ms 8448 KB
67.txt 3 ms 8448 KB