Submission #1887485

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 200200;
const int MIN = 20;

int A[MAX];
VI V;

int L[MIN][MAX];
int R[MIN][MAX];

int DP1[1<<MIN];
int DP2[1<<MIN];

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int n, v;
	scanf("%d%d", &n, &v);

	FOR (i, 0, n)
	{
		scanf("%d", &A[i]);
	}

	while(v > 0)
	{
		V.PB(v);
		v /= 2;
	}

	V.PB(0);

	int m = SZ(V);

	FOR (it, 0, m)
	{
		int w = V[it];

		L[it][0] = 0;

		FOR (i, 1, n)
		{
			if (A[i] - A[i-1] <= w) L[it][i] = L[it][i-1];
			else L[it][i] = i;
		}

		R[it][n-1] = n-1;
		RFOR(i, n-1, 0)
		{
			if (A[i+1] - A[i] <= w) R[it][i] = R[it][i+1];
			else R[it][i] = i;
		}
	}


	FOR (mask, 0, 1<<m)
	{
		int ind = DP1[mask];

		FOR (i, 0, m)
		{
			if (mask & (1<<i)) continue;
			int nm = mask | (1<<i);
			if (ind == n)
			{
				DP1[nm] = n;
				continue;
			}

			int to = R[i][ind] + 1;

			DP1[nm] = max(DP1[nm], to);
		}
	}

	FOR (mask, 0, 1<<m)
	{
		DP2[mask] = n-1;
	}

	FOR (mask, 0, 1<<m)
	{
		int ind = DP2[mask];

		FOR (i, 0, m)
		{
			if (mask & (1<<i)) continue;
			int nm = mask | (1<<i);
			if (ind == -1)
			{
				DP2[nm] = -1;
				continue;
			}

			int to = L[i][ind] - 1;
			DP2[nm] = min(DP2[nm], to);
		}
	}

	int x = 0;
	while(x < n)
	{
		int to = R[0][x];

		bool ok = false;

		FOR (mask, 0, 1<<m)
		{
			if (mask & (1<<0)) continue;
			int m1 = mask;
			int m2 = (((1<<m)-1) - (1<<0)) ^ m1;

			if (DP1[m1] >= x && DP2[m2] <= to ) ok = true;
		}

		string res;
		if (ok) res = "Possible";
		else res = "Impossible";

		while(x <= to)
		{
			printf("%s\n", res.c_str());
			x++;
		}
	}


}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:40: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:44:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
                     ^

Judge Result