#include <bits/stdc++.h> #define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cerr<<#x<<" "<<x<<endl #define ll long long #define st first #define nd second using namespace std; ll n, t, a[500005], res[500005], pref[500005], temp, ile[500005], roz; pair<ll, ll> p[500005]; int main() { qio; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; p[i] = { a[i],i }; } sort(p + 1, p + n + 1); p[0] = p[1]; for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + p[i].st; } for (int i = 1; i <= n; i++) { if (p[i].st != p[i - 1].st) roz++; if (roz == 0) ile[i] = p[i].st; else ile[i] = pref[i]; //cout << ile[i] << endl; } for (int i = n; i >= 1 && roz > 0; i--) { if (ile[i] > p[i + 1].st) { res[p[i].nd] = 1; } else { break; } } for (int i = 1; i <= n; i++) { if (res[i] == 1) 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 | #include <bits/stdc++.h> #define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cerr<<#x<<" "<<x<<endl #define ll long long #define st first #define nd second using namespace std; ll n, t, a[500005], res[500005], pref[500005], temp, ile[500005], roz; pair<ll, ll> p[500005]; int main() { qio; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; p[i] = { a[i],i }; } sort(p + 1, p + n + 1); p[0] = p[1]; for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + p[i].st; } for (int i = 1; i <= n; i++) { if (p[i].st != p[i - 1].st) roz++; if (roz == 0) ile[i] = p[i].st; else ile[i] = pref[i]; //cout << ile[i] << endl; } for (int i = n; i >= 1 && roz > 0; i--) { if (ile[i] > p[i + 1].st) { res[p[i].nd] = 1; } else { break; } } for (int i = 1; i <= n; i++) { if (res[i] == 1) cout << "T"; else cout << "N"; } cout << endl; } |