#include <iostream> #include <algorithm> #include <map> int n; int T[500005]; int t[500005]; long long s[500005]; std::map<long long, bool> m; void input() { std::cin >> n; for (int i = 0; i < n; i++) { int k; std::cin >> k; T[i] = k; t[i] = k; } } void solve() { std::sort(t, t + n); s[0] = t[0]; for (int i = 1; i < n; ++i) { s[i] = s[i - 1] + t[i]; } m[t[n - 1]] = true; int next = t[n - 1]; int i = n - 2; while (i >= 0) { int j = i; while (j > 0 && t[j] == t[j - 1]) { --j; } // std::cout << i << " " << j << "\n"; if (j == 0) { m[t[j]] = false; } else { long long k = s[i]; std::map<long long, bool>::iterator it = m.lower_bound(k); if (it == m.begin()) { m[t[j]] = false; } else { // std::cout << "it" << it->first << " " << it->second << "\n"; --it; // std::cout << "decreased\n"; m[t[j]] = it->second; } } i = j - 1; } // std::cout << "FINISHED\n"; for (int i = 0; i < n; i++) { std::cout << (m[T[i]] ? 'T' : 'N'); } std::cout << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); input(); solve(); 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 67 68 69 | #include <iostream> #include <algorithm> #include <map> int n; int T[500005]; int t[500005]; long long s[500005]; std::map<long long, bool> m; void input() { std::cin >> n; for (int i = 0; i < n; i++) { int k; std::cin >> k; T[i] = k; t[i] = k; } } void solve() { std::sort(t, t + n); s[0] = t[0]; for (int i = 1; i < n; ++i) { s[i] = s[i - 1] + t[i]; } m[t[n - 1]] = true; int next = t[n - 1]; int i = n - 2; while (i >= 0) { int j = i; while (j > 0 && t[j] == t[j - 1]) { --j; } // std::cout << i << " " << j << "\n"; if (j == 0) { m[t[j]] = false; } else { long long k = s[i]; std::map<long long, bool>::iterator it = m.lower_bound(k); if (it == m.begin()) { m[t[j]] = false; } else { // std::cout << "it" << it->first << " " << it->second << "\n"; --it; // std::cout << "decreased\n"; m[t[j]] = it->second; } } i = j - 1; } // std::cout << "FINISHED\n"; for (int i = 0; i < n; i++) { std::cout << (m[T[i]] ? 'T' : 'N'); } std::cout << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); input(); solve(); return 0; } |