Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.math.*;
- import java.security.*;
- import java.text.*;
- import java.util.*;
- import java.util.concurrent.*;
- import java.util.regex.*;
- import java.util.stream.*;
- public class Solution {
- // Complete the climbingLeaderboard function below.
- static int[] climbingLeaderboard(int[] scores, int[] alice) {
- ArrayList<Integer> sorted = new ArrayList<>(scores.length);
- for (int i = 0; i < scores.length; i++) {
- if (sorted.isEmpty() || sorted.get(sorted.size() - 1) != scores[i]) {
- sorted.add(scores[i]);
- }
- }
- int[] positions = new int[alice.length];
- int size = sorted.size();
- for (int i = 0; i < alice.length; i++) {
- if (i > 0 && alice[i] == alice[i-1]) {
- positions[i] = positions[i - 1];
- continue;
- }
- if (i > 0 && positions[i - 1] > 1 && alice[i] < sorted.get(positions[i - 1] - 2)) {
- positions[i] = positions[i - 1];
- continue;
- }
- if (sorted.get(size - 1) > alice[i]) {
- positions[i] = size + 1;
- } else if (sorted.get(0) < alice[i]) {
- positions[i] = 1;
- } else {
- int end = i > 0 ? positions[i - 1] : size;
- positions[i] = binSearch(sorted, 0, end, alice[i]) + 1;
- }
- }
- return positions;
- }
- static int binSearch(List<Integer> arr, int start, int end, int goal) {
- if (arr.get(start) == goal) {
- return start;
- }
- int theEnd = end >= arr.size() ? arr.size() - 1 : end;
- if (arr.get(theEnd) == goal) {
- return theEnd;
- }
- if (end - start <= 1) {
- return start + 1;
- } else {
- int pivot = (end - start) / 2 + start;
- System.out.println("pivot " + pivot + " goal " + goal);
- if (arr.get(pivot) == goal) {
- return pivot;
- }
- if (arr.get(pivot) < goal) {
- return binSearch(arr, start, pivot, goal);
- } else {
- return binSearch(arr, pivot, end, goal);
- }
- }
- }
- private static final Scanner scanner = new Scanner(System.in);
- public static void main(String[] args) throws IOException {
- BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
- int scoresCount = scanner.nextInt();
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- int[] scores = new int[scoresCount];
- String[] scoresItems = scanner.nextLine().split(" ");
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- for (int i = 0; i < scoresCount; i++) {
- int scoresItem = Integer.parseInt(scoresItems[i]);
- scores[i] = scoresItem;
- }
- int aliceCount = scanner.nextInt();
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- int[] alice = new int[aliceCount];
- String[] aliceItems = scanner.nextLine().split(" ");
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- for (int i = 0; i < aliceCount; i++) {
- int aliceItem = Integer.parseInt(aliceItems[i]);
- alice[i] = aliceItem;
- }
- int[] result = climbingLeaderboard(scores, alice);
- for (int i = 0; i < result.length; i++) {
- bufferedWriter.write(String.valueOf(result[i]));
- if (i != result.length - 1) {
- bufferedWriter.write("\n");
- }
- }
- bufferedWriter.newLine();
- bufferedWriter.close();
- scanner.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement