#include <iostream> #include <map> #include <algorithm> #include <utility> using namespace std; #define st first #define nd second const int N = 500001, BASE = (1<<19); int n, arr[N], s; pair <int, int> pom[N]; bool sc[N]; map <int, int> M; int main() { ios_base::sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; pom[i] = { arr[i], i }; } sort(pom, pom + n); s += pom[0].st; for (int i = 1; i < n; i++) { s += pom[i].st; if (pom[i].st != pom[i - 1].st) { if (s > pom[n - 1].st) sc[pom[i].nd] = 1; } else { sc[pom[i].nd] = sc[pom[i - 1].nd]; } } for (int i = 0; i < n; i++) { if (sc[i] == 1) cout << "T"; else cout << "N"; } }
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 | #include <iostream> #include <map> #include <algorithm> #include <utility> using namespace std; #define st first #define nd second const int N = 500001, BASE = (1<<19); int n, arr[N], s; pair <int, int> pom[N]; bool sc[N]; map <int, int> M; int main() { ios_base::sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; pom[i] = { arr[i], i }; } sort(pom, pom + n); s += pom[0].st; for (int i = 1; i < n; i++) { s += pom[i].st; if (pom[i].st != pom[i - 1].st) { if (s > pom[n - 1].st) sc[pom[i].nd] = 1; } else { sc[pom[i].nd] = sc[pom[i - 1].nd]; } } for (int i = 0; i < n; i++) { if (sc[i] == 1) cout << "T"; else cout << "N"; } } |