#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; } |
English