Approach
Sorting and greedy selection
For ABC299 B — Trick Taking, 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
- 51 lines of C++ from the credited upstream file abc299_b.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 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 <map>4#include <vector>5 6using namespace std;7using ui = unsigned int;8 9struct Player {10 ui no;11 ui c;12 ui r;13};14 15bool comp(Player& l, Player& r) { return l.r < r.r; }16 17int main() {18 ui n, t;19 cin >> n >> t;20 21 vector<Player> p(n);22 map<ui, vector<Player>> cp;23 24 for (ui i = 0; i < n; i++) {25 ui c;26 cin >> c;27 p[i].no = i + 1;28 p[i].c = c;29 }30 31 for (ui i = 0; i < n; i++) {32 ui r;33 cin >> r;34 p[i].r = r;35 }36 37 for (auto& pp : p) {38 cp[pp.c].push_back(pp);39 }40 41 if (cp.count(t) == 0) {42 t = p[0].c;43 }44 45 vector<Player> cand = cp[t];46 47 sort(cand.rbegin(), cand.rend(), comp);48 49 cout << cand[0].no << endl;50 return 0;51}