SHARE
TWEET

SegmentsAndPoints

a guest Mar 29th, 2016 191 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class SegmentsAndPoints {
  4.   static final int N = 100;
  5.   static final int M = 500;
  6.  
  7.   boolean order(int l, int x, int r) {
  8.     return l <= x && x <= r;
  9.   }
  10.  
  11.   public String checkData(int[] p, int[] l, int[] r) {
  12.     if (p.length != l.length || p.length != r.length)
  13.       return "p, l and r must contain the same number of elements.";
  14.  
  15.     if (!order(1, p.length, N))
  16.       return "p must contain between 1 and 100 elements, inclusive.";
  17.  
  18.     for (int i = 0; i < p.length; ++i)
  19.       if (l[i] > r[i])
  20.         return "l[i] must be not greater than r[i] for each i.";
  21.  
  22.     for (int i = 0; i < p.length; ++i)
  23.       if (!order(-M, p[i], M))
  24.         return "Each element of p must be between -500 and 500, inclusive.";
  25.  
  26.     for (int i = 0; i < p.length; ++i)
  27.       if (!order(-M, l[i], M))
  28.         return "Each element of l must be between -500 and 500, inclusive.";
  29.        
  30.     for (int i = 0; i < p.length; ++i)
  31.       if (!order(-M, r[i], M))
  32.         return "Each element of r must be between -500 and 500, inclusive.";
  33.  
  34.     return "";
  35.   }
  36.  
  37.  
  38.   public String isPossible(int[] p, int[] l, int[] r) {
  39.     int n = p.length;
  40.     boolean[] open = new boolean[n];
  41.     boolean[] done = new boolean[n];
  42.    
  43.     for (int i = -M; i <= M; ++i) {
  44.       for (int j = 0; j < n; ++j)
  45.         if (l[j] == i)
  46.           open[j] = true;
  47.  
  48.       for (int j = 0; j < n; ++j)
  49.         if (p[j] == i) {
  50.           int best = -1;
  51.           for (int k = 0; k < n; ++k)
  52.             if (open[k] && !done[k] && (best == -1 || r[best] > r[k]))
  53.               best = k;
  54.  
  55.           if (best == -1)
  56.             return "Impossible";
  57.  
  58.           done[best] = true;
  59.         }
  60.  
  61.       for (int j = 0; j < n; ++j)
  62.         if (r[j] == i)
  63.           open[j] = false;
  64.     }
  65.  
  66.     return "Possible";
  67.   }
  68.  
  69.   public static void main(String[] args) {
  70.     SegmentsAndPoints solver = new SegmentsAndPoints();
  71.     int[] p = {0};
  72.     int[] l = {1};
  73.     int[] r = {1};
  74.     System.out.println(solver.checkData(p, l, r));
  75.     System.out.println(solver.isPossible(p, l, r));
  76.   }
  77. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top