Submission #6772157


Source Code Expand

Copy
#include <cstdio>
#include <iostream>
#define MN 201000

int n, v;
int a[MN];
int f[MN], g[MN];
int b[MN];
int nxt[20][MN];
int lst[20][MN];

int main()
{
	scanf("%d%d", &n, &v);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int x = v;
	int m = 0;
	while(x) {b[m++] = x / 2; x /= 2;}
	b[m] = v;
	
	for(int i = 0; i <= m; i++)
	{
		lst[i][1] = 1;
		for(int j = 2; j <= n; j++)
		{
			if(a[j] - a[j - 1] <= b[i]) lst[i][j] = lst[i][j - 1];
			else lst[i][j] = j;
		}
	}
	
	int tot = 0;
	for(int i = 0; i <= m; i++)
	{
		nxt[i][n] = n;
		for(int j = n - 1; j >= 1; j--)
		{
			if(a[j + 1] - a[j] <= b[i]) nxt[i][j] = nxt[i][j + 1];
			else {nxt[i][j] = j; if(i == m) tot++;}
		}
	}
	
	if(m < tot) 
	{
		for(int i = 1; i <= n; i++) puts("Impossible");
		return 0;
	}
	
	for(int S = 0; S < (1 << m); S++) g[S] = n + 1; 
	for(int S = 0; S < (1 << m); S++)
	{
		for(int i = 0; i < m; i++)
		{
			if(!((S >> i) & 1))
			{
				f[S | (1 << i)] = std::max(f[S | (1 << i)], nxt[i][f[S] + 1]);
				g[S | (1 << i)] = std::min(g[S | (1 << i)], lst[i][g[S] - 1]);
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		bool ok = 0;
		for(int S = 0; S < (1 << m); S++)
		{
			int T = ((1 << m) - 1) ^ S;
			if(f[S] >= i - 1 && g[T] <= nxt[m][i] + 1) {ok = 1; break;}
		}
		for(int j = i; j <= nxt[m][i]; j++)
		{
			if(ok) puts("Possible");
			else puts("Impossible");
		}
		i = nxt[m][i];
	}
}

Submission Info

Submission Time
Task E - Camel and Oases
User luhong
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1449 Byte
Status
Exec Time 159 ms
Memory 36864 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &v);
                       ^
./Main.cpp:15:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
                                                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
× 3
× 34
× 8
× 28
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 3 ms 6400 KB
00_example_02.txt 3 ms 6400 KB
00_example_03.txt 4 ms 10496 KB
01.txt 31 ms 32256 KB
02.txt 15 ms 29184 KB
03.txt 31 ms 32256 KB
04.txt 14 ms 29184 KB
05.txt 30 ms 32256 KB
06.txt 130 ms 32512 KB
07.txt 18 ms 29696 KB
08.txt 126 ms 32384 KB
09.txt 19 ms 29696 KB
10.txt 124 ms 32256 KB
11.txt 26 ms 32128 KB
12.txt 126 ms 32384 KB
13.txt 158 ms 34816 KB
14.txt 122 ms 32256 KB
15.txt 15 ms 29184 KB
16.txt 126 ms 32256 KB
17.txt 14 ms 29184 KB
18.txt 122 ms 32256 KB
19.txt 21 ms 31488 KB
20.txt 127 ms 32512 KB
21.txt 18 ms 29696 KB
22.txt 126 ms 32512 KB
23.txt 19 ms 29824 KB
24.txt 124 ms 32384 KB
25.txt 25 ms 32000 KB
26.txt 126 ms 32512 KB
27.txt 159 ms 34816 KB
28.txt 38 ms 32768 KB
29.txt 18 ms 29696 KB
30.txt 35 ms 32768 KB
31.txt 24 ms 31872 KB
32.txt 33 ms 32512 KB
33.txt 25 ms 32000 KB
34.txt 34 ms 32640 KB
35.txt 73 ms 36864 KB
36.txt 122 ms 32256 KB
37.txt 15 ms 29184 KB
38.txt 124 ms 32256 KB
39.txt 15 ms 29184 KB
40.txt 121 ms 32256 KB
41.txt 21 ms 31488 KB
42.txt 122 ms 32256 KB
43.txt 21 ms 31488 KB
44.txt 123 ms 32256 KB
45.txt 20 ms 31488 KB
46.txt 18 ms 29568 KB
47.txt 125 ms 32384 KB
48.txt 24 ms 31872 KB
49.txt 124 ms 32384 KB
50.txt 24 ms 31872 KB
51.txt 125 ms 32384 KB
52.txt 24 ms 31872 KB
53.txt 125 ms 32384 KB
54.txt 24 ms 31872 KB
55.txt 125 ms 32384 KB
56.txt 16 ms 29440 KB
57.txt 126 ms 32384 KB
58.txt 24 ms 31872 KB
59.txt 125 ms 32384 KB
60.txt 25 ms 32000 KB
61.txt 125 ms 32384 KB
62.txt 24 ms 31872 KB
63.txt 125 ms 32384 KB
64.txt 25 ms 32000 KB
65.txt 125 ms 32384 KB
66.txt 4 ms 6400 KB
67.txt 3 ms 6400 KB