SegmentsAndPoints

import java.util.*;

public class SegmentsAndPoints {
  static final int N = 100;
  static final int M = 500;

  boolean order(int l, int x, int r) {
    return l <= x && x <= r;
  }

  public String checkData(int[] p, int[] l, int[] r) {
    if (p.length != l.length || p.length != r.length)
      return "p, l and r must contain the same number of elements.";

    if (!order(1, p.length, N))
      return "p must contain between 1 and 100 elements, inclusive.";

    for (int i = 0; i < p.length; ++i)
      if (l[i] > r[i])
        return "l[i] must be not greater than r[i] for each i.";

    for (int i = 0; i < p.length; ++i)
      if (!order(-M, p[i], M))
        return "Each element of p must be between -500 and 500, inclusive.";

    for (int i = 0; i < p.length; ++i)
      if (!order(-M, l[i], M))
        return "Each element of l must be between -500 and 500, inclusive.";

    for (int i = 0; i < p.length; ++i)
      if (!order(-M, r[i], M))
        return "Each element of r must be between -500 and 500, inclusive.";

    return "";
  }


  public String isPossible(int[] p, int[] l, int[] r) {
    int n = p.length;
    boolean[] open = new boolean[n];
    boolean[] done = new boolean[n];

    for (int i = -M; i <= M; ++i) {
      for (int j = 0; j < n; ++j)
        if (l[j] == i)
          open[j] = true;

      for (int j = 0; j < n; ++j)
        if (p[j] == i) {
          int best = -1;
          for (int k = 0; k < n; ++k)
            if (open[k] && !done[k] && (best == -1 || r[best] > r[k]))
              best = k;

          if (best == -1)
            return "Impossible";

          done[best] = true;
        }

      for (int j = 0; j < n; ++j)
        if (r[j] == i)
          open[j] = false;
    }

    return "Possible";
  }

  public static void main(String[] args) {
    SegmentsAndPoints solver = new SegmentsAndPoints();
    int[] p = {0};
    int[] l = {1};
    int[] r = {1};
    System.out.println(solver.checkData(p, l, r));
    System.out.println(solver.isPossible(p, l, r));
  }
};