Approach
Sorting and greedy selection
For ABC113 C — ID, 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
- 70 lines of C++ from the credited upstream file abc113_c.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 7 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 <tuple>5#include <vector>6 7using namespace std;8 9bool comp_year(const tuple<unsigned int, unsigned int, unsigned int>& l,10 const tuple<unsigned int, unsigned int, unsigned int>& r) {11 return get<0>(l) < get<0>(r);12}13 14string gen_code(const unsigned int& p, const unsigned int& idx) {15 string code(12, '_');16 17 unsigned int i = 0;18 for (i = 0; i < 6 - to_string(p).length(); i++) {19 code[i] = '0';20 }21 22 for (auto& c : to_string(p)) {23 code[i] = c;24 i++;25 }26 27 for (; i < 12 - to_string(idx).length(); i++) {28 code[i] = '0';29 }30 31 for (auto& c : to_string(idx)) {32 code[i] = c;33 i++;34 }35 36 return code;37}38 39int main() {40 unsigned int n, m;41 cin >> n >> m;42 43 vector<tuple<unsigned int, unsigned int, unsigned int>> y_i_list(44 m); 45 for (unsigned int i = 0; i < m; i++) {46 unsigned int p, y;47 cin >> p >> y;48 y_i_list[i] = {y, i, p};49 }50 51 sort(y_i_list.begin(), y_i_list.end(), comp_year);52 53 map<unsigned int, unsigned int> p_c;54 vector<string> codes(m, "");55 for (auto& yi : y_i_list) {56 if (p_c.count(get<2>(yi)) == 0) {57 p_c[get<2>(yi)] = 1;58 } else {59 p_c[get<2>(yi)]++;60 }61 62 codes[get<1>(yi)] = gen_code(get<2>(yi), p_c[get<2>(yi)]);63 }64 65 for (auto& c : codes) {66 cout << c << endl;67 }68 69 return 0;70}