Approach
Sorting and greedy selection
For ABC355 B — Piano 2, 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
- 41 lines of C++ from the credited upstream file abc355_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 8bool comp(pair<ui, char>& l, pair<ui, char>& r) { return l.first < r.first; }9 10int main() {11 ui n, m;12 cin >> n >> m;13 14 vector<pair<ui, char>> c(n + m);15 ui i = 0;16 17 for (; i < n; i++) {18 cin >> c[i].first;19 c[i].second = 'a';20 }21 for (; i < m + n; i++) {22 cin >> c[i].first;23 c[i].second = 'b';24 }25 26 sort(c.begin(), c.end(), comp);27 28 char p = '.';29 for (auto& cc : c) {30 if (cc.second == p && cc.second == 'a') {31 cout << "Yes" << endl;32 return 0;33 }34 35 p = cc.second;36 }37 38 cout << "No" << endl;39 40 return 0;41}