Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.73 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.  
  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.             if (i > 0 && alice[i] == alice[i-1]) {
  25.                 positions[i] = positions[i - 1];
  26.                 continue;
  27.             }
  28.             if (i > 0 && positions[i - 1] > 1 && alice[i] < sorted.get(positions[i - 1] - 2)) {
  29.                 positions[i] = positions[i - 1];
  30.                 continue;
  31.             }
  32.             if (sorted.get(size - 1) > alice[i]) {
  33.                 positions[i] = size + 1;
  34.             } else if (sorted.get(0) < alice[i]) {
  35.                 positions[i] = 1;    
  36.             } else {
  37.                 int end = i > 0 ? positions[i - 1] : size;
  38.                 positions[i] = binSearch(sorted, 0, end, alice[i]) + 1;
  39.             }
  40.         }
  41.         return positions;
  42.     }
  43.  
  44.     static int binSearch(List<Integer> arr, int start, int end, int goal) {
  45.         if (arr.get(start) == goal) {
  46.             return start;
  47.         }
  48.         int theEnd = end >= arr.size() ? arr.size() - 1 : end;
  49.         if (arr.get(theEnd) == goal) {
  50.             return theEnd;
  51.         }
  52.         if (end - start <= 1) {
  53.             return start + 1;
  54.         } else {
  55.             int pivot = (end - start) / 2 + start;
  56.             System.out.println("pivot " + pivot + " goal " + goal);
  57.             if (arr.get(pivot) == goal) {
  58.                 return pivot;
  59.             }
  60.             if (arr.get(pivot) < goal) {
  61.                 return binSearch(arr, start, pivot, goal);
  62.             } else {
  63.                 return binSearch(arr, pivot, end, goal);
  64.             }
  65.         }
  66.     }
  67.     private static final Scanner scanner = new Scanner(System.in);
  68.  
  69.     public static void main(String[] args) throws IOException {
  70.         BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  71.  
  72.         int scoresCount = scanner.nextInt();
  73.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  74.  
  75.         int[] scores = new int[scoresCount];
  76.  
  77.         String[] scoresItems = scanner.nextLine().split(" ");
  78.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  79.  
  80.         for (int i = 0; i < scoresCount; i++) {
  81.             int scoresItem = Integer.parseInt(scoresItems[i]);
  82.             scores[i] = scoresItem;
  83.         }
  84.  
  85.         int aliceCount = scanner.nextInt();
  86.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  87.  
  88.         int[] alice = new int[aliceCount];
  89.  
  90.         String[] aliceItems = scanner.nextLine().split(" ");
  91.         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  92.  
  93.         for (int i = 0; i < aliceCount; i++) {
  94.             int aliceItem = Integer.parseInt(aliceItems[i]);
  95.             alice[i] = aliceItem;
  96.         }
  97.  
  98.         int[] result = climbingLeaderboard(scores, alice);
  99.  
  100.         for (int i = 0; i < result.length; i++) {
  101.             bufferedWriter.write(String.valueOf(result[i]));
  102.  
  103.             if (i != result.length - 1) {
  104.                 bufferedWriter.write("\n");
  105.             }
  106.         }
  107.  
  108.         bufferedWriter.newLine();
  109.  
  110.         bufferedWriter.close();
  111.  
  112.         scanner.close();
  113.     }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement