Approach
Sorting and greedy selection
For ABC260 B — Better Students Are Needed!, 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
- 73 lines of C++ from the credited upstream file abc260_b.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 8bool compA(pair<ui, pair<ui, ui>>& l, pair<ui, pair<ui, ui>>& r) {9 if (l.second.first != r.second.first)10 return l.second.first > r.second.first;11 return l.first < r.first;12}13 14bool compB(pair<ui, pair<ui, ui>>& l, pair<ui, pair<ui, ui>>& r) {15 if (l.second.second != r.second.second)16 return l.second.second > r.second.second;17 return l.first < r.first;18}19 20bool compC(pair<ui, pair<ui, ui>>& l, pair<ui, pair<ui, ui>>& r) {21 if (l.second.first + l.second.second != r.second.first + r.second.second)22 return l.second.first + l.second.second >23 r.second.first + r.second.second;24 return l.first < r.first;25}26 27void out(vector<ui>& v) {28 sort(v.begin(), v.end());29 for (auto& vv : v) cout << vv << endl;30}31 32int main() {33 ui n, x, y, z;34 cin >> n >> x >> y >> z;35 36 vector<ui> ans;37 38 vector<pair<ui, pair<ui, ui>>> s(n);39 for (ui i = 0; i < n; i++) {40 cin >> s[i].second.first;41 s[i].first = i + 1;42 }43 44 for (ui i = 0; i < n; i++) cin >> s[i].second.second;45 46 sort(s.rbegin(), s.rend(), compA);47 for (ui i = 0; i < x; i++) {48 ans.push_back(s[s.size() - 1].first);49 s.pop_back();50 }51 52 if (s.size() == 0) {53 out(ans);54 return 0;55 }56 57 sort(s.rbegin(), s.rend(), compB);58 for (ui i = 0; i < y; i++) {59 ans.push_back(s[s.size() - 1].first);60 s.pop_back();61 }62 63 if (s.size() == 0) {64 out(ans);65 return 0;66 }67 68 sort(s.begin(), s.end(), compC);69 for (ui i = 0; i < z; i++) ans.push_back(s[i].first);70 71 out(ans);72 return 0;73}