Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //NB: or the judge to run the program you must use the default package
- //NB: Importing other classes is NOT ALLOWED
- import java.util.Scanner;
- // NB: For the judge to run the program, do not modify the declaration of the class Main or
- // method main() below. The class has to be declared as "class Main { ... }"
- // and the method as "public static void main(String[] args) { ... }"
- class Main
- {
- //mountain_cities[i] is the position of the (i+1)-th mountain city
- //sea_cities[i] is the position of the (i+1)-th sea city
- //trip_beginning[i] and trip_end[i] are the beginning and ending kilometers of the (i+1)-th trip
- //The number of elements of an array A can be accessed using A.length
- public static int solve(int n, int[] mountain_cities, int[] sea_cities, int[] trip_beginning, int[] trip_end)
- {
- heapSort(sea_cities);
- heapSort(mountain_cities);
- int[] trips = new int[trip_beginning.length];
- int maxTrip = 0;
- for(int i = 0; i < trip_beginning.length; i++){
- int tripSeaCities = citiesInTrip(sea_cities, trip_beginning[i], trip_end[i]);
- trips[i] = citiesInTrip(mountain_cities, trip_beginning[i], trip_end[i]);
- if(tripSeaCities == 0){
- if(trips[i] > trips[maxTrip]){
- maxTrip = i;
- }
- }else{trips[i] = 0;}
- }
- return maxTrip+1;
- }
- public static void printArray(int[] A){
- System.out.print(A[0]);
- for(int i = 1; i < A.length; i++){
- System.out.print(", " + A[i]);
- }
- System.out.println();
- }
- public static int citiesInTrip(int[] cityList, int startKil, int endKil){
- int[] startIndex = binarySearch(cityList, startKil);
- int[] endIndex = binarySearch(cityList, endKil);
- if(startIndex[1] < 0 && endIndex[1] < 0){
- return Math.abs(endIndex[0]-startIndex[0]);
- }
- else if(startIndex[1] < 0){
- startIndex[0] = startIndex[0] + 1;
- }
- return endIndex[0]-startIndex[0] + 1;
- }
- public static int[] binarySearch(int[] A, int key){
- int start = 0;
- int end = A.length-1;
- int m = end/2;
- while (end >= start){
- if(key < A[m]){
- end = m-1;
- }
- else if(key > A[m]){
- start = m+1;
- }
- else{
- return new int[] {m,1};
- }
- m = (int)(Math.min(start, end) + Math.abs((end-start)/2));
- }
- return new int[] {m,-1};
- }
- static void sinkDown(int[] A, int startIndex, int endIndex){
- int i = startIndex;
- int j = 2*i;
- while(j <= endIndex){
- if(j+1 <= endIndex){
- if(A[j+1] > A[j]){
- j++;
- }
- }
- if(A[j] > A[i]){
- int temp = A[i];
- A[i] = A[j];
- A[j] = temp;
- }
- else{
- j = A.length;
- }
- i = j;
- j = 2*j;
- }
- }
- static void initializeHeap(int[] A){
- for(int i = A.length/2; i < A.length; i++){
- sinkDown(A, A.length-1-i, A.length-1);
- }
- }
- static void heapSort(int[] A){
- initializeHeap(A);
- for(int i = 0; i < A.length; i++){
- int temp = A[A.length-1-i];
- A[A.length-1-i] = A[0];
- A[0] = temp;
- sinkDown(A, 0, A.length-1-i-1);
- }
- }
- public static void main(String[] args)
- {
- Scanner scanner = new Scanner(System.in);
- int ntestcases = scanner.nextInt();
- for(int testno=0; testno<ntestcases; testno++)
- {
- int n = scanner.nextInt();
- int M = scanner.nextInt();
- int S = scanner.nextInt();
- int T = scanner.nextInt();
- int[] mountain_cities = new int[M];
- for(int i=0; i<M; i++)
- mountain_cities[i] = scanner.nextInt();
- int[] sea_cities = new int[S];
- for(int i=0; i<S; i++)
- sea_cities[i] = scanner.nextInt();
- int[] trip_beginning = new int[T];
- for(int i=0; i<T; i++)
- trip_beginning[i] = scanner.nextInt();
- int[] trip_end = new int[T];
- for(int i=0; i<T; i++)
- trip_end[i] = scanner.nextInt();
- System.out.println(solve(n, mountain_cities, sea_cities, trip_beginning, trip_end));
- }
- scanner.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement