Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Ignore the order for a moment. If the game ended right now, what is each player's final score ? The winner must have final score equal to .
The annoying tie rule only matters between players whose final score is exactly . Anyone who reached early but later fell below the maximum is irrelevant. Yep, that's the trap.
Since the tie rule talks about who reached at least first, you probably need the chronological log twice: once to know , once to simulate prefixes.
After computing all final totals, replay the rounds with prefix scores . The first time you see a player such that and , that player is the answer.
Algorithm in one line: store all rounds, compute final scores , set , replay rounds accumulating current scores, and print the first name satisfying
The final maximum score matters first. Let
and
Only players with can possibly win. The statement says that if several players have the maximum final score, then among them the winner is the one who first scored at least points.
That word “them” is doing real work. A player might reach early, then lose points and finish below . That player is not a candidate. Don't let that guy steal the trophy like a gremlin.
The rounds are chronological, but we don't know until the game is over. So we do this:
is the winner.
At the end, candidates are exactly the players with final score .
For each candidate , during the replay their prefix score eventually becomes at the latest by their final update, because their final score is exactly . So at least one candidate will satisfy .
The tie-breaking rule asks for the candidate who reaches at least earliest in chronological order. Our second pass checks rounds in chronological order, so the first satisfying player is exactly the required winner.
This also handles negative scores cleanly. A candidate may reach , drop below it, and later finish at again. The first time still counts. A non-candidate may reach too, but we ignore them because .
Let be the number of rounds. Using a hash map for scores:
expected, and
for storing the log and the players' scores. With , this is hilariously safe.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int n;
cin >> n;
vector<pair<string, int>> rounds(n);
unordered_map<string, int> total;
for (int i = 0; i < n; i++) {
string name;
int score;
cin >> name >> score;
rounds[i] = {name, score};
total[name] += score;
}
int best = numeric_limits<int>::min();
for (const auto& [name, score] : total) {
best = max(best, score);
}
unordered_map<string, int> current;
for (const auto& [name, score] : rounds) {
current[name] += score;
if (total[name] == best && current[name] >= best) {
cout << name << '\n';
return 0;
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int n;
cin >> n;
vector<pair<string, int>> rounds(n);
unordered_map<string, int> total;
for (int i = 0; i < n; i++) {
string name;
int score;
cin >> name >> score;
rounds[i] = {name, score};
total[name] += score;
}
int best = numeric_limits<int>::min();
for (const auto& [name, score] : total) {
best = max(best, score);
}
unordered_map<string, int> current;
for (const auto& [name, score] : rounds) {
current[name] += score;
if (total[name] == best && current[name] >= best) {
cout << name << '\n';
return 0;
}
}
return 0;
}