Let’s build the leaderboard first. Let  denote the rank of the  player in the leaderboard. We can calculate  from the scores of the players. Recall that the ranking rules are as follows:

The player with the highest score is ranked .

Players with the same score receive the same rank.

Rank increases by  for each distinct, lower score.

The function below assigns rank  to the first score. Each distinct subsequent score’s rank increases by , so equal (tied) scores have the same rank. When this array is completed, we’ll have an array of ranks that directly corresponds to the array of scores such that each rank index matches each score index:

#define mx 200000
int s[mx+1];
int rank[mx+1];
void build_rank(int n){
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            rank[i] = 1;
        }
        else {
            if (s[i] == s[i-1]) {
                rank[i] = rank[i - 1];
            }
            else {
                rank[i] = rank[i - 1] + 1;
            }
        }
    }
}

Solution

One approach to determining the rank for each of the player’s level scores with the lowest score in the leaderboard. If her score is larger than the leaderboard’s current top score, we’ll continue iterating through the scores in the leaderboard and stop when we find a score that the player’s current total score is not greater than. If the player’s score is equal to the current leaderboard score, we’ll look up that score in the rank array (created above) for the rank value and print that value  (because arrays are zero-indexed). If the player’s score is less than the current leaderboard score, we’ll need to add one to the rank and then add one again when we print it (because of the zero-indexing). Take some time to review the Python solution below for more detail.

#include <bits/stdc++.h>

using namespace std;

#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

#define mx 200000
int s[mx + 1];
int rank[mx + 1];
int a[mx + 1];
void build_rank(int n){
    for (int i=0;i<n;i++) {
        if (i==0) {
            rank[i] = 1;
        }
        else {
            if (s[i] == s[i-1]) {
                rank[i] = rank[i - 1];
            }
            else {
                rank[i] = rank[i - 1] + 1 ;
            }
        }
    }
}

int main(){
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }
    build_rank(n);
    
    int m;
    int point = n;
    cin >> m;
    for (int j = 0; j < m; j++) {
        cin >> a[j];
    }
   
    for(int j = 0; j < m; j++) {
        
        int current_rank;
    
        while (point >= 0 and a[j] > s[point]) {
            point--;
        }
        
        if (point == -1) {
            current_rank = 1;
        }
        else if (a[j] == s[point]) {
            current_rank = rank[point];
        }
        else if (a[j] < s[point]) {
            current_rank = rank[point] + 1;
        }
        cout << current_rank << endl;
    }
    return 0;
}
def climbingLeaderboard(ranked,player):

    # get a list of unique scores, still sorted descending
    scores = []
    i = 0
    lr = len(ranked)
    while i < lr:
        cur = ranked[i]
        scores.append(cur)
        while i < lr and cur == ranked[i]:
            i += 1
            
    n = len(scores)
    ans = []
    
    # initialize pointer outside the loop
    # the scores are sorted, so this prevents
    # iterating lower scores again
    i = 0
    
    # the index provides the ranking (n - i + 1)
    
    for score in player:
	    # work from right to left in scores array
        while i < n and scores[n - i - 1] <= score:
            i += 1
            
        ans.append(n - i + 1)
        
    return ans

Leave a reply