Approach
Sorting and greedy selection
For ABC399 B — Ranking with Ties, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 42 lines of C++ from the credited upstream file abc399_b.cpp.
- The implementation visibly relies on sequence storage.
- 3 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <vector>4 5using namespace std;6using ui = unsigned int;7 8int main() {9 ui n;10 cin >> n;11 12 vector<pair<ui, ui>> p(n, {0, 0});13 vector<pair<ui, ui>> pv(n);14 for (ui i = 0; i < n; i++) {15 cin >> p[i].first;16 pv[i] = {p[i].first, i};17 }18 19 sort(pv.rbegin(), pv.rend(),20 [](const pair<ui, ui>& a, const pair<ui, ui>& b) {21 return a.first < b.first;22 });23 24 ui r = 1;25 ui prev = pv[0].first;26 ui t = 0;27 for (auto const& pvv : pv) {28 if (pvv.first != prev) {29 r += t;30 t = 1;31 } else {32 t++;33 }34 35 p[pvv.second].second = r;36 prev = pvv.first;37 }38 39 for (auto const& pp : p) cout << pp.second << endl;40 41 return 0;42}