This has been asked a couple of times but here is my implementation in C++. I have 11/12 solutions completed. The 6th test case which has 200000 intial scores and Alice has even more scores causes my program to timeout. Below is the problem statement and the code. My question is, am I missing something in code complexity, or is this a more of a C++ optimization I need to add to get the last test data set through?
Problem
Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. The game uses Dense Ranking, so its leaderboard works like this:
The player with the highest score is ranked number 1 on the leaderboard. Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number. For example, the four players on the leaderboard have high scores of , , , and . Those players will have ranks 100, 90, 90, and 80, respectively. If Alice's scores are 70, 80 and 105, her rankings after each game are 4th, 3rd and 1st.
Function Description
Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element
res[j]
represents Alice's rank after thej
-th game.climbingLeaderboard has the following parameter(s):
scores
: an array of integers that represent leaderboard scoresalice
: an array of integers that represent Alice's scoresInput Format
The first line contains an integer
n
, the number of players on the leaderboard. The next line containsn
space-separated integersscores[i]
, the leaderboard scores in decreasing order. The next line contains an integer,m
, denoting the number games Alice plays. The last line containsm
space-separated integersalice[j]
, the game scores.Constraints
The existing leaderboard, scores, is in descending order. Alice's scores, alice, are in ascending order.
Output Format
m
integers. Thej
-th integer should indicate Alice's rank after playing thej
-th game.
Code
std::vector<int>::iterator m_binary_search(std::vector<int>::iterator begin,
std::vector<int>::iterator end, int score)
{
std::vector<int>::iterator ret;
if (score > (*begin)) {
return begin;
} else if (score < (*(end - 1))) {
return end - 1;
}
if (*begin == score) {
ret = begin;
} else if (*(end - 1) == score) {
ret = end - 1;
} else if (begin + 1 == end) {
ret = begin;
} else {
std::ptrdiff_t middle = std::distance(begin, end) / 2;
if (*(begin + middle) == score) {
ret = begin + middle;
} else if ((score < (*begin)) && (score > * (begin + middle))) {
ret = m_binary_search(begin, begin + middle, score);
} else {
ret = m_binary_search(begin + middle, end, score);
}
}
return ret;
}
// Complete the climbingLeaderboard function below.
std::vector<int> climbingLeaderboard(
const std::vector<int> &scores,
const std::vector<int> &alice)
{
std::vector<int> rankBuckets;
for (std::size_t s = 0; s < scores.size();) {
int curr = scores[s];
while (s < scores.size() && scores[s] == curr) {
++s;
}
rankBuckets.push_back(curr);
}
typedef std::vector<int>::iterator VectIt_t;
std::vector<int> ranks;
for (int score : alice) {
VectIt_t cit = m_binary_search(
rankBuckets.begin(),
rankBuckets.end(),
score);
VectIt_t nit = cit;
++nit;
std::ptrdiff_t rank = std::distance(rankBuckets.begin(), cit);
if (nit == rankBuckets.end()) {
if (*cit != score) {
rankBuckets.push_back(score);
rank += 2;
} else {
rank += 1;
}
ranks.push_back(rank);
continue;
}
int crank = *cit;
int nrank = *nit;
if (score > crank) {
rankBuckets.insert(cit, score);
rank += 1;
} else if (score == crank) {
rank += 1;
} else if (score < crank && score > nrank) {
rankBuckets.insert(nit, score);
rank += 2;
}
ranks.push_back(rank);
}
return ranks;
}