The Silver Score
National Olympiad — National round (2018 season)
Submission name: silver.cpp
Problem summary
Every competitor with the maximum score wins gold. Silver goes to competitors with the largest score strictly below the maximum. Find this silver score.
Source clarification. All-equal scores satisfy the printed numeric bounds but have no silver medalist. The PDF gives no output rule for that case. The solution covers inputs with at least two distinct scores; otherwise it reports a diagnostic to stderr and returns exit status 1 without inventing a judge answer.
Input
n, followed by n positive integer scores.
Output
The second-largest distinct score.
Constraints
1 < n < 1000000; 1 ≤ score ≤ 100000000; memory limit 2 MB. The PDF does not define an answer if all scores are equal.
Worked example
An independently prepared example for this explanation.
Input
9 5 8 1 8 6 2 6 3 8
Output
6
Solution analysis
- Keep only the largest and second-largest distinct scores seen so far. This meets the small memory limit without storing or sorting the input.
- When a score exceeds the current maximum, the old maximum becomes the silver candidate. Otherwise, if it is strictly below the maximum but above the silver candidate, replace the silver candidate. A score equal to the maximum changes nothing.
- For 5,8,1,8,6,2,6,3,8, the maximum is 8. Repeated 8s still win gold; the largest score below them is 6. If no lower distinct score exists, the statement supplies no required answer; the code reports that undefined case on the error stream and exits unsuccessfully.
Why it works
After each score, the two variables hold the largest and second-largest distinct scores in the processed prefix, using zero when no such positive score exists. Each update preserves this invariant by considering whether the new score creates a new maximum, a new second maximum, or neither. Thus the second variable is the silver score whenever silver exists.
Watch out. Second-largest means distinct: another gold score is not silver. Do not allocate an array under the 2 MB memory limit.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int maximum = 0;
int second = 0;
for (int i = 0; i < n; ++i) {
int score;
cin >> score;
// Equal maximum scores are gold again, never a silver candidate.
if (score > maximum) {
second = maximum;
maximum = score;
} else if (score < maximum && score > second) {
second = score;
}
}
if (second == 0) {
cerr << "No silver score is defined for all-equal input.\n";
return 1;
}
cout << second << '\n';
}