Approach
Sorting and greedy selection
For ABC150 C — Count Order, 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
- 67 lines of C++ from the credited upstream file abc150_c.cpp.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup.
- 5 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;7 8void gen(unsigned int& len, string s, unsigned int pos, vector<bool> used,9 vector<string>& dict) {10 s += to_string(pos + 1);11 used[pos] = true;12 13 if (s.length() == len) {14 dict.push_back(s);15 return;16 }17 18 for (unsigned int i = 0; i < used.size(); i++) {19 if (used[i]) {20 continue;21 }22 23 gen(len, s, i, used, dict);24 }25}26 27int main() {28 unsigned int n;29 cin >> n;30 31 vector<string> dict;32 for (unsigned int i = 0; i < n; i++) {33 vector<bool> used(n, false);34 string s = "";35 gen(n, s, i, used, dict);36 }37 38 sort(dict.begin(), dict.end());39 40 map<string, unsigned int> so;41 unsigned int ord = 1;42 for (auto& s : dict) {43 so[s] = ord;44 ord++;45 }46 47 string p(n, '.');48 for (unsigned int i = 0; i < n; i++) {49 cin >> p[i];50 }51 52 string q(n, '.');53 for (unsigned int i = 0; i < n; i++) {54 cin >> q[i];55 }56 57 unsigned int ans = 0;58 if (so[p] > so[q]) {59 ans = so[p] - so[q];60 } else {61 ans = so[q] - so[p];62 }63 64 cout << ans << endl;65 66 return 0;67}