Advertisement
Guest User

Untitled

a guest
Nov 19th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.78 KB | None | 0 0
  1. //NB: or the judge to run the program you must use the default package
  2.  
  3. //NB: Importing other classes is NOT ALLOWED
  4. import java.util.Scanner;
  5.  
  6. // NB: For the judge to run the program, do not modify the declaration of the class Main or
  7. // method main() below. The class has to be declared as "class Main { ... }"
  8. // and the method as "public static void main(String[] args) { ... }"
  9. class Main
  10. {
  11.     //mountain_cities[i] is the position of the (i+1)-th mountain city
  12.     //sea_cities[i] is the position of the (i+1)-th sea city
  13.     //trip_beginning[i] and trip_end[i] are the beginning and ending kilometers of the (i+1)-th trip
  14.     //The number of elements of an array A can be accessed using A.length
  15.     public static int solve(int n, int[] mountain_cities, int[] sea_cities, int[] trip_beginning, int[] trip_end)
  16.     {
  17.                 heapSort(sea_cities);
  18.                 heapSort(mountain_cities);
  19.         int[] trips = new int[trip_beginning.length];
  20.                 int maxTrip = 0;
  21.                 for(int i = 0; i < trip_beginning.length; i++){
  22.                     int tripSeaCities = citiesInTrip(sea_cities, trip_beginning[i], trip_end[i]);
  23.                     trips[i] = citiesInTrip(mountain_cities, trip_beginning[i], trip_end[i]);
  24.                     if(tripSeaCities == 0){
  25.                         if(trips[i] > trips[maxTrip]){
  26.                             maxTrip = i;
  27.                         }
  28.                     }else{trips[i] = 0;}
  29.                 }
  30.         return maxTrip+1;
  31.     }
  32.  
  33.     public static void printArray(int[] A){
  34.         System.out.print(A[0]);
  35.         for(int i = 1; i < A.length; i++){
  36.             System.out.print(", " + A[i]);
  37.         }
  38.         System.out.println();
  39.     }
  40.  
  41.     public static int citiesInTrip(int[] cityList, int startKil, int endKil){
  42.         int[] startIndex = binarySearch(cityList, startKil);
  43.         int[] endIndex = binarySearch(cityList, endKil);
  44.  
  45.         if(startIndex[1] < 0 && endIndex[1] < 0){
  46.             return Math.abs(endIndex[0]-startIndex[0]);
  47.         }
  48.         else if(startIndex[1] < 0){
  49.             startIndex[0] = startIndex[0] + 1;
  50.         }
  51.  
  52.         return endIndex[0]-startIndex[0] + 1;
  53.     }
  54.  
  55.     public static int[] binarySearch(int[] A, int key){
  56.         int start = 0;
  57.         int end = A.length-1;
  58.         int m = end/2;
  59.         while (end >= start){
  60.             if(key < A[m]){
  61.                 end = m-1;
  62.             }
  63.             else if(key > A[m]){
  64.                 start = m+1;
  65.             }
  66.             else{
  67.                 return new int[] {m,1};
  68.             }
  69.             m = (int)(Math.min(start, end) + Math.abs((end-start)/2));
  70.         }
  71.         return new int[] {m,-1};
  72.     }
  73.  
  74.     static void sinkDown(int[] A, int startIndex, int endIndex){
  75.         int i = startIndex;
  76.         int j = 2*i;
  77.         while(j <= endIndex){
  78.             if(j+1 <= endIndex){
  79.                 if(A[j+1] > A[j]){
  80.                     j++;
  81.                 }
  82.             }
  83.             if(A[j] > A[i]){
  84.                 int temp = A[i];
  85.                 A[i] = A[j];
  86.                 A[j] = temp;
  87.             }
  88.             else{
  89.                 j = A.length;
  90.             }
  91.             i = j;
  92.             j = 2*j;
  93.         }
  94.     }
  95.  
  96.     static void initializeHeap(int[] A){
  97.         for(int i = A.length/2; i < A.length; i++){
  98.             sinkDown(A, A.length-1-i, A.length-1);
  99.         }
  100.     }
  101.  
  102.     static void heapSort(int[] A){
  103.         initializeHeap(A);
  104.         for(int i = 0; i < A.length; i++){
  105.             int temp = A[A.length-1-i];
  106.             A[A.length-1-i] = A[0];
  107.             A[0] = temp;
  108.             sinkDown(A, 0, A.length-1-i-1);
  109.         }
  110.     }
  111.  
  112.     public static void main(String[] args)
  113.     {
  114.         Scanner scanner = new Scanner(System.in);
  115.         int ntestcases = scanner.nextInt();
  116.  
  117.         for(int testno=0; testno<ntestcases; testno++)
  118.         {
  119.             int n = scanner.nextInt();
  120.             int M = scanner.nextInt();
  121.             int S = scanner.nextInt();
  122.             int T = scanner.nextInt();
  123.  
  124.             int[] mountain_cities = new int[M];
  125.             for(int i=0; i<M; i++)
  126.                 mountain_cities[i] = scanner.nextInt();
  127.  
  128.             int[] sea_cities = new int[S];
  129.             for(int i=0; i<S; i++)
  130.                 sea_cities[i] = scanner.nextInt();
  131.  
  132.             int[] trip_beginning = new int[T];
  133.             for(int i=0; i<T; i++)
  134.                 trip_beginning[i] = scanner.nextInt();
  135.  
  136.             int[] trip_end = new int[T];
  137.             for(int i=0; i<T; i++)
  138.                 trip_end[i] = scanner.nextInt();
  139.  
  140.             System.out.println(solve(n, mountain_cities, sea_cities, trip_beginning, trip_end));
  141.         }
  142.  
  143.         scanner.close();
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement