#include <bits/stdc++.h> using namespace std; vector <bool> solve(int n, vector <int> &arr) { vector <pair<int,int>> valAndIdx(n); for (int i = 0; i < n; i++) { valAndIdx[i] = {arr[i], i}; } sort(valAndIdx.begin(), valAndIdx.end()); vector <long long> prefSum(n); for (int i = 0; i < n; i++) { prefSum[i] = valAndIdx[i].first; if (i > 0) { prefSum[i] += prefSum[i - 1]; } } int maxBad = 0; for (int i = 0; i < n - 1; i++) { if (prefSum[i] <= valAndIdx[i + 1].first) { maxBad = i; } } vector <bool> ans(n, false); for (int i = maxBad + 1; i < n; i++) { ans[valAndIdx[i].second] = true; } int r = 0; while (r < n - 1 && valAndIdx[r + 1].first == valAndIdx[0].first) { r++; } if (r > 0) { for (int i = 0; i <= r; i++) { ans[valAndIdx[i].second] = false; } } return ans; } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; vector <int> arr(n); for (int &ai : arr) { cin >> ai; } auto ans = solve(n, arr); for (int i = 0; i < n; i++) { cout << (ans[i] ? 'T' : '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 62 63 64 65 66 | #include <bits/stdc++.h> using namespace std; vector <bool> solve(int n, vector <int> &arr) { vector <pair<int,int>> valAndIdx(n); for (int i = 0; i < n; i++) { valAndIdx[i] = {arr[i], i}; } sort(valAndIdx.begin(), valAndIdx.end()); vector <long long> prefSum(n); for (int i = 0; i < n; i++) { prefSum[i] = valAndIdx[i].first; if (i > 0) { prefSum[i] += prefSum[i - 1]; } } int maxBad = 0; for (int i = 0; i < n - 1; i++) { if (prefSum[i] <= valAndIdx[i + 1].first) { maxBad = i; } } vector <bool> ans(n, false); for (int i = maxBad + 1; i < n; i++) { ans[valAndIdx[i].second] = true; } int r = 0; while (r < n - 1 && valAndIdx[r + 1].first == valAndIdx[0].first) { r++; } if (r > 0) { for (int i = 0; i <= r; i++) { ans[valAndIdx[i].second] = false; } } return ans; } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; vector <int> arr(n); for (int &ai : arr) { cin >> ai; } auto ans = solve(n, arr); for (int i = 0; i < n; i++) { cout << (ans[i] ? 'T' : 'N'); } return 0; } |