#include <bits/stdc++.h> #define int long long using namespace std; struct sumy { long long val; int cnt; bool is_smallest; bool is_biggest; }; const bool operator<(const sumy &lhs, const sumy &rhs) { return lhs.val < rhs.val; } void print_sum(sumy sum) { cerr << "ile " << sum.cnt << " waga " << sum.val << " maly " << sum.is_smallest << " duzy " << sum.is_biggest << endl; } bool is_worthy(sumy sum, int index, const vector<sumy> &prefix_sums, int current_smallest) { if (sum.is_smallest) { return false; } else if (sum.is_biggest) { return true; } else { return prefix_sums[index].val > current_smallest; } } signed main() { int n; cin >> n; vector<int> sums(n); map<int, int> weight_cnt; vector<sumy> sorted_sums; vector<sumy> prefix_sums; int smallest = 1'000'000'001; int biggest = -1; int smallest_ok = smallest; for (int i = 0; i < n; i++) { cin >> sums[i]; weight_cnt[sums[i]]++; if (sums[i] > biggest) { biggest = sums[i]; } if (sums[i] < smallest) { smallest = sums[i]; } } for (auto &[k, v] : weight_cnt) { bool is_smallest = k == smallest; bool is_biggest = k == biggest; sorted_sums.push_back({k, v, is_smallest, is_biggest}); prefix_sums.push_back({k, v, is_smallest, is_biggest}); } sort(sorted_sums.begin(), sorted_sums.end()); sort(prefix_sums.begin(), prefix_sums.end()); prefix_sums[0].val *= prefix_sums[0].cnt; int k = sorted_sums.size(); for (int i = 1; i < k; i++) { prefix_sums[i].val = prefix_sums[i].val * prefix_sums[i].cnt + prefix_sums[i - 1].val; } for (int i = k - 1; i >= 0; i--) { if (is_worthy(sorted_sums[i], i, prefix_sums, smallest_ok)) { smallest_ok = sorted_sums[i].val; } else { break; } } // for (int i = 0; i < k; i++) { // print_sum(sorted_sums[i]); // } // cerr << endl; // for (int i = 0; i < k; i++) { // print_sum(prefix_sums[i]); // } for (int i = 0; i < n; i++) { if (sums[i] >= smallest_ok) { cout << 'T'; } else { cout << 'N'; } } cout << endl; }
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <bits/stdc++.h> #define int long long using namespace std; struct sumy { long long val; int cnt; bool is_smallest; bool is_biggest; }; const bool operator<(const sumy &lhs, const sumy &rhs) { return lhs.val < rhs.val; } void print_sum(sumy sum) { cerr << "ile " << sum.cnt << " waga " << sum.val << " maly " << sum.is_smallest << " duzy " << sum.is_biggest << endl; } bool is_worthy(sumy sum, int index, const vector<sumy> &prefix_sums, int current_smallest) { if (sum.is_smallest) { return false; } else if (sum.is_biggest) { return true; } else { return prefix_sums[index].val > current_smallest; } } signed main() { int n; cin >> n; vector<int> sums(n); map<int, int> weight_cnt; vector<sumy> sorted_sums; vector<sumy> prefix_sums; int smallest = 1'000'000'001; int biggest = -1; int smallest_ok = smallest; for (int i = 0; i < n; i++) { cin >> sums[i]; weight_cnt[sums[i]]++; if (sums[i] > biggest) { biggest = sums[i]; } if (sums[i] < smallest) { smallest = sums[i]; } } for (auto &[k, v] : weight_cnt) { bool is_smallest = k == smallest; bool is_biggest = k == biggest; sorted_sums.push_back({k, v, is_smallest, is_biggest}); prefix_sums.push_back({k, v, is_smallest, is_biggest}); } sort(sorted_sums.begin(), sorted_sums.end()); sort(prefix_sums.begin(), prefix_sums.end()); prefix_sums[0].val *= prefix_sums[0].cnt; int k = sorted_sums.size(); for (int i = 1; i < k; i++) { prefix_sums[i].val = prefix_sums[i].val * prefix_sums[i].cnt + prefix_sums[i - 1].val; } for (int i = k - 1; i >= 0; i--) { if (is_worthy(sorted_sums[i], i, prefix_sums, smallest_ok)) { smallest_ok = sorted_sums[i].val; } else { break; } } // for (int i = 0; i < k; i++) { // print_sum(sorted_sums[i]); // } // cerr << endl; // for (int i = 0; i < k; i++) { // print_sum(prefix_sums[i]); // } for (int i = 0; i < n; i++) { if (sums[i] >= smallest_ok) { cout << 'T'; } else { cout << 'N'; } } cout << endl; } |