#include <iostream> #include <vector> #include <algorithm> #include <set> #include <numeric> using namespace std; int main() { int n; cin >> n; if (n == 1) { cout << "T\n"; return 0; } vector<long long> weights(n); for (int i = 0; i < n; ++i) { long long weight; cin >> weight; weights[i] = weight; } vector<long long> sorted_weights(weights); sort(sorted_weights.begin(), sorted_weights.end()); long long weight_sum = reduce(sorted_weights.begin(), sorted_weights.end(), (long long) 0); set<long long> kings; for (int i = n - 1; i >= 0; --i) { int the_same_weight = 1; while (i > 0 && sorted_weights[i-1] == sorted_weights[i]) { the_same_weight++; i--; } if (weight_sum - the_same_weight * sorted_weights[i] == 0) { break; } if (kings.empty() || weight_sum > *(kings.begin())) { kings.insert(sorted_weights[i]); } weight_sum -= the_same_weight * sorted_weights[i]; } for (long long weight : weights) { if (!kings.empty() && weight >= *kings.begin()) { cout << 'T'; } else { cout << 'N'; } } cout << '\n'; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <iostream> #include <vector> #include <algorithm> #include <set> #include <numeric> using namespace std; int main() { int n; cin >> n; if (n == 1) { cout << "T\n"; return 0; } vector<long long> weights(n); for (int i = 0; i < n; ++i) { long long weight; cin >> weight; weights[i] = weight; } vector<long long> sorted_weights(weights); sort(sorted_weights.begin(), sorted_weights.end()); long long weight_sum = reduce(sorted_weights.begin(), sorted_weights.end(), (long long) 0); set<long long> kings; for (int i = n - 1; i >= 0; --i) { int the_same_weight = 1; while (i > 0 && sorted_weights[i-1] == sorted_weights[i]) { the_same_weight++; i--; } if (weight_sum - the_same_weight * sorted_weights[i] == 0) { break; } if (kings.empty() || weight_sum > *(kings.begin())) { kings.insert(sorted_weights[i]); } weight_sum -= the_same_weight * sorted_weights[i]; } for (long long weight : weights) { if (!kings.empty() && weight >= *kings.begin()) { cout << 'T'; } else { cout << 'N'; } } cout << '\n'; return 0; } |