Approach
Sorting and greedy selection
For ABC323 B — Round-Robin 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
- 44 lines of C++ from the credited upstream file abc323_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 <tuple>4#include <vector>5 6using namespace std;7 8bool comp(const tuple<int, int>& lhs, const tuple<int, int>& rhs) {9 if (std::get<1>(lhs) != std::get<1>(rhs)) {10 return std::get<1>(lhs) < std::get<1>(rhs);11 }12 return std::get<0>(lhs) > std::get<0>(rhs);13}14 15int main() {16 int N = 0;17 cin >> N;18 19 vector<tuple<int, int>> u;20 21 for (int i = 0; i < N; i++) {22 string s = "";23 cin >> s;24 int c = 0;25 for (unsigned long si = 0; si < s.length(); si++) {26 if (s[si] == 'o') {27 c++;28 }29 }30 31 u.push_back({i + 1, c});32 }33 34 sort(u.rbegin(), u.rend(), comp);35 36 for (unsigned long i = 0; i < u.size(); i++) {37 if (i > 0) {38 cout << " ";39 }40 cout << get<0>(u[i]);41 }42 43 cout << endl;44}