Advertisement
Douma37

Climbing the leaderboard

Apr 24th, 2019
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.23 KB | None | 0 0
  1. import java.io.*;
  2. import java.math.*;
  3. import java.security.*;
  4. import java.text.*;
  5. import java.util.*;
  6. import java.util.concurrent.*;
  7. import java.util.regex.*;
  8. import java.util.stream.*;
  9.  
  10. public class Solution {
  11.  
  12.     // Complete the climbingLeaderboard function below.
  13.     static int[] climbingLeaderboard(int[] scores, int[] alice) {
  14.         // remove duplicates from the leaderboard
  15.         ArrayList<Integer> sorted = new ArrayList<>(scores.length);
  16.         for (int i = 0; i < scores.length; i++) {
  17.             if (sorted.isEmpty() || sorted.get(sorted.size() - 1) != scores[i]) {
  18.                 sorted.add(scores[i]);
  19.             }
  20.         }
  21.         int[] positions = new int[alice.length];
  22.         int size = sorted.size();      
  23.         for (int i = 0; i < alice.length; i++) {
  24.             // Alice scored the same twice in a row, so reuse previous value
  25.             if (i > 0 && alice[i] == alice[i-1]) {
  26.                 positions[i] = positions[i - 1];
  27.                 continue;
  28.             }
  29.             // Alice scored a bit better, but is still in the same position
  30.             if (i > 0 && positions[i - 1] > 1 && alice[i] < sorted.get(positions[i - 1] - 2)) {
  31.                 positions[i] = positions[i - 1];
  32.                 continue;
  33.             }
  34.             // last position
  35.             if (sorted.get(size - 1) > alice[i]) {
  36.                 positions[i] = size + 1;
  37.             } else if (sorted.get(0) < alice[i]) {
  38.                 // first
  39.                 positions[i] = 1;    
  40.             } else {
  41.                 // otherwise, bin search
  42.                 // indexOf has linear search because accepts general object
  43.                 int end = i > 0 ? positions[i - 1] : size;
  44.                 positions[i] = binSearch(sorted, 0, end, alice[i]) + 1;
  45.             }
  46.         }
  47.         return positions;
  48.     }
  49.  
  50.     static int binSearch(List<Integer> arr, int start, int end, int goal) {
  51.         if (arr.get(start) == goal) {
  52.             return start;
  53.         }
  54.         // somehow end can be beyond the end of the array. Deal with it
  55.         int theEnd = end >= arr.size() ? arr.size() - 1 : end;
  56.         if (arr.get(theEnd) == goal) {
  57.             return theEnd;
  58.         }
  59.         if (end - start <= 1) {
  60.             // no match, but we narrowed down the bracket
  61.             return start + 1;
  62.         } else {
  63.             int pivot = (end - start) / 2 + start;
  64.             System.out.println("pivot " + pivot + " goal " + goal);
  65.             if (arr.get(pivot) == goal) {
  66.                 return pivot;
  67.             }
  68.             if (arr.get(pivot) < goal) {
  69.                 return binSearch(arr, start, pivot, goal);
  70.             } else {
  71.                 return binSearch(arr, pivot, end, goal);
  72.             }
  73.         }
  74.     }
  75.     private static final Scanner scanner = new Scanner(System.in);
  76.  
  77.     public static void main(String[] args) throws IOException {
  78.         BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  79.  
  80.         int scoresCount = scanner.nextInt();
  81.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  82.  
  83.         int[] scores = new int[scoresCount];
  84.  
  85.         String[] scoresItems = scanner.nextLine().split(" ");
  86.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  87.  
  88.         for (int i = 0; i < scoresCount; i++) {
  89.             int scoresItem = Integer.parseInt(scoresItems[i]);
  90.             scores[i] = scoresItem;
  91.         }
  92.  
  93.         int aliceCount = scanner.nextInt();
  94.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  95.  
  96.         int[] alice = new int[aliceCount];
  97.  
  98.         String[] aliceItems = scanner.nextLine().split(" ");
  99.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  100.  
  101.         for (int i = 0; i < aliceCount; i++) {
  102.             int aliceItem = Integer.parseInt(aliceItems[i]);
  103.             alice[i] = aliceItem;
  104.         }
  105.  
  106.         int[] result = climbingLeaderboard(scores, alice);
  107.  
  108.         for (int i = 0; i < result.length; i++) {
  109.             bufferedWriter.write(String.valueOf(result[i]));
  110.  
  111.             if (i != result.length - 1) {
  112.                 bufferedWriter.write("\n");
  113.             }
  114.         }
  115.  
  116.         bufferedWriter.newLine();
  117.  
  118.         bufferedWriter.close();
  119.  
  120.         scanner.close();
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement