Submission #1453641

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int N, V;
int K;
int L[20];
int X[200000];
int U[200000];
int F[20][200000];
bool B[200000];
int dp[2][1<<20];

int find(int x) {
  if (U[x] == x) return x;
  return U[x] = find(U[x]);
}

void unite(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (x < y) swap(x, y);
  U[y] = x;
}

bool same(int x, int y) {
  return find(x) == find(y);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> V;
  rep(i, N) cin >> X[i];
  int t = V;
  //L[K++] = t;
  while (t > 0) {
    t /= 2;
    L[K++] = t;
  }

  rep(e, 2) {
    rep(k, K) {
      rep(i, N) U[i] = i;
      rep(i, N-1) {
        int d = abs(X[i+1]-X[i]);
        if (d <= L[k]) unite(i, i+1);
      }
      rep(i, N) F[k][i] = find(i);
    }
    dp[e][0] = 0;
    rep(b, 1<<K) {
      int x = dp[e][b];
      rep(i, K) {
        if ((1<<i) & b) continue;
        int nx = x;
        if (x != N) nx = F[i][x]+1;
        int nb = b | (1<<i);
        dp[e][nb] = max(dp[e][nb], nx);
      }
    }
    reverse(X, X+N);
  }

  rep(i, N) U[i] = i;
  rep(i, N-1) {
    int d = X[i+1]-X[i];
    if (d <= V) unite(i, i+1);
  }
  rep(lb, 1<<K) {
    int rb = ((1<<K)-1) ^ lb;
    int a = dp[0][lb],
        b = N-1-(dp[1][rb]);
    if (a > b) {
      // all possible
      rep(i, N) {
        cout << "Possible\n";
      }
      return 0;
    }
    if (same(a, b)) {
      B[find(a)] = true;
    }
  }

  rep(x, N) {
    if (B[find(x)]) cout << "Possible\n";
    else cout << "Impossible\n";
  }
  return 0;
}

Submission Info

Judge Result