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

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]);
                                                ^

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 0 / 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 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
07.txt 18 ms 29696 KB
08.txt
09.txt 19 ms 29696 KB
10.txt
11.txt 26 ms 32128 KB
12.txt
13.txt
14.txt
15.txt 15 ms 29184 KB
16.txt
17.txt 14 ms 29184 KB
18.txt
19.txt 21 ms 31488 KB
20.txt
21.txt 18 ms 29696 KB
22.txt
23.txt 19 ms 29824 KB
24.txt
25.txt 25 ms 32000 KB
26.txt
27.txt
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
37.txt 15 ms 29184 KB
38.txt
39.txt 15 ms 29184 KB
40.txt
41.txt 21 ms 31488 KB
42.txt
43.txt 21 ms 31488 KB
44.txt
45.txt 20 ms 31488 KB
46.txt 18 ms 29568 KB
47.txt
48.txt 24 ms 31872 KB
49.txt
50.txt 24 ms 31872 KB
51.txt
52.txt 24 ms 31872 KB
53.txt
54.txt 24 ms 31872 KB
55.txt
56.txt 16 ms 29440 KB
57.txt
58.txt 24 ms 31872 KB
59.txt
60.txt 25 ms 32000 KB
61.txt
62.txt 24 ms 31872 KB
63.txt
64.txt 25 ms 32000 KB
65.txt
66.txt 4 ms 6400 KB
67.txt 3 ms 6400 KB