I have been doing this challenge in which I need to determine and return one's (i.e. alice
) rank on a leaderboard by comparing her scores to the others'. I made this work in all but this one case where there are 200000 scores on the board, so I believe my program is not effective at large scale. I am receiving a timeout error. I tried to shorten the program as much as possible but I think loops are still too much of a problem. I would appreciate any suggestions.
#include <bits/stdc++.h>
using namespace std;
vector <int> climbingLeaderboard(vector <int> scores, vector <int> alice) {
vector<int> result;
reverse(alice.begin(), alice.end());
int lastIndex = 0;
int lastRank = 1;
for (int i = 0; i < alice.size(); i++) {
int rank = lastRank;
for (int j = lastIndex; j < scores.size(); j++) {
if (alice[i] >= scores[j]) {
lastIndex = j;
break;
}
else if (alice[i] < scores[j]) {
rank++;
}
if (scores[j] == scores[j+1] && rank != 1) {
rank--;
}
}
result.push_back(rank);
lastRank = rank;
}
reverse(result.begin(), result.end());
return result;
}
int main() {
int n;
cin >> n;
vector<int> scores(n);
for(int scores_i = 0; scores_i < n; scores_i++){
cin >> scores[scores_i];
}
int m;
cin >> m;
vector<int> alice(m);
for(int alice_i = 0; alice_i < m; alice_i++){
cin >> alice[alice_i];
}
vector <int> result = climbingLeaderboard(scores, alice);
for (ssize_t i = 0; i < result.size(); i++) {
cout << result[i] << (i != result.size() - 1 ? "\n" : "");
}
cout << endl;
return 0;
}
Sample Input
7
100 100 50 40 40 20 10
4
5 25 50 120
Sample Output
6
4
2
1
Explanation
The second row of input is composed of the scores on the leaderboard and the fourth row contains the scores of Alice. The score she gets during each attempt is compared with other scores on the leaderboard to determine her rank. Dense Ranking is used here. So from the sample input, the first two 100
s on the leaderboard rank 1st and then 50
ranks the 2nd, both 40
s rank 3rd and so on.