2AUnreviewed1500GPT-5.5 (high)

Winner

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

hashing implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

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 $S_x$ ? The winner must have final score equal to $m = \max_x S_x$ .

The annoying tie rule only matters between players whose final score is exactly $m$ . Anyone who reached $m$ early but later fell below the maximum is irrelevant. Yep, that's the trap.

Since the tie rule talks about who reached at least $m$ first, you probably need the chronological log twice: once to know $m$ , once to simulate prefixes.

After computing all final totals, replay the rounds with prefix scores $P_x$ . The first time you see a player $x$ such that $S_x = m$ and $P_x \ge m$ , that player is the answer.

Algorithm in one line: store all rounds, compute final scores $S_x$ , set $m=\max S_x$ , replay rounds accumulating current scores, and print the first name satisfying $S_x=m \quad\text{and}\quad P_x\ge m.$

Key observation

The final maximum score matters first. Let

S_x = \text{final score of player } x

and

m = \max_x S_x.

Only players with $S_x = m$ 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 $m$ points.

That word “them” is doing real work. A player might reach $m$ early, then lose points and finish below $m$ . That player is not a candidate. Don't let that guy steal the trophy like a gremlin.

Two-pass strategy

The rounds are chronological, but we don't know $m$ until the game is over. So we do this:

Read and store all rounds.
Compute every player's final score $S_x$ .
Find

m = \max_x S_x.

Replay the rounds from the beginning, maintaining prefix/current scores $P_x$ .
The first player $x$ such that

S_x = m \quad \text{and} \quad P_x \ge m

is the winner.

Why this works

At the end, candidates are exactly the players with final score $m$ .

For each candidate $x$ , during the replay their prefix score eventually becomes $m$ at the latest by their final update, because their final score is exactly $m$ . So at least one candidate will satisfy $P_x \ge m$ .

The tie-breaking rule asks for the candidate who reaches at least $m$ 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 $m$ , drop below it, and later finish at $m$ again. The first time still counts. A non-candidate may reach $m$ too, but we ignore them because $S_x \ne m$ .

Complexity

Let $n$ be the number of rounds. Using a hash map for scores:

\text{Time} = O(n)

expected, and

\text{Memory} = O(n)

for storing the log and the players' scores. With $n \le 1000$ , 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;
}

View on Codeforces Back to the list