Approach
Sorting and greedy selection
For ABC222 C — Swiss-System Tournament, 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
- 65 lines of C++ from the credited upstream file abc222_c.cpp.
- The implementation visibly relies on sequence storage.
- 6 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 8struct U {9 ui i, w;10};11 12bool comp(const U& l, const U& r) {13 if (l.w != r.w) return l.w > r.w;14 15 return l.i < r.i;16}17 18int main() {19 ui n, m;20 cin >> n >> m;21 22 vector<U> u(n * 2);23 for (ui i = 0; i < 2 * n; i++) u[i] = {i, 0};24 25 vector<vector<char>> j(2 * n, vector<char>(m, '.'));26 for (auto& jj : j)27 for (auto& a : jj) cin >> a;28 29 for (ui i = 0; i < m; i++) {30 for (ui k = 1; k <= n; k++) {31 U *a = &u[k * 2 - 2], *b = &u[k * 2 - 1];32 switch (j[a->i][i]) {33 case 'G':34 if (j[b->i][i] == 'C')35 a->w++;36 else if (j[b->i][i] == 'P')37 b->w++;38 break;39 40 case 'C':41 if (j[b->i][i] == 'P')42 a->w++;43 else if (j[b->i][i] == 'G')44 b->w++;45 break;46 47 case 'P':48 if (j[b->i][i] == 'G')49 a->w++;50 else if (j[b->i][i] == 'C')51 b->w++;52 break;53 54 default:55 break;56 }57 }58 59 sort(u.begin(), u.end(), comp);60 }61 62 for (auto& uu : u) cout << uu.i + 1 << endl;63 64 return 0;65}