Approach
Sorting and greedy selection
For ARC146 A — Three Cards, 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
- 54 lines of C++ from the credited upstream file arc146_a.cpp.
- The implementation visibly relies on sequence storage.
- 4 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;6 7bool comp_length(const string& lhs, const string& rhs) {8 if (lhs.size() != rhs.size()) {9 return lhs.size() < rhs.size();10 }11 12 for (unsigned int i = 0; i < lhs.size(); i++) {13 if (lhs[i] != rhs[i]) {14 return lhs[i] < rhs[i];15 }16 }17 18 return true;19}20 21bool comp_value(const string& lhs, const string& rhs) {22 for (unsigned int i = 0; i < min(lhs.size(), rhs.size()); i++) {23 if (lhs[i] != rhs[i]) {24 return lhs[i] < rhs[i];25 }26 }27 28 return true;29}30 31int main() {32 unsigned int N = 0;33 cin >> N;34 35 vector<string> A(N, "");36 for (auto& a : A) {37 cin >> a;38 }39 40 sort(A.rbegin(), A.rend(), comp_length);41 vector<string> A2 = {A[0], A[1], A[2]};42 if (A2[0].size() != A2[1].size() || A2[1].size() != A2[2].size() ||43 A2[1].size() != A2[0].size()) {44 sort(A2.rbegin(), A2.rend(), comp_value);45 }46 47 for (auto& a2 : A2) {48 cout << a2;49 }50 51 cout << endl;52 53 return 0;54}