#include <iostream> #include <vector> #include <algorithm> const int N = 500005; long long sumsOrd[N]; long long *sums[N]; bool ptrCmp(long long *a, long long *b) { return *a < *b; } int main() { int n; std::cin >> n; for (int i=0; i<n; i++) { long long s; std::cin >> s; sumsOrd[i] = s; sums[i] = &sumsOrd[i]; } std::sort(sums, sums + n, ptrCmp); std::vector<long long> prefixSum; prefixSum.resize(n + 1); int it=0; long long lastWeight = *sums[0]; while (it < n) { int start = it; while (it < n && lastWeight == *sums[it]) {it++;} long long newPrefSum; // = prefixSum[start-1]; if (start == 0) { newPrefSum = *sums[start]; } else { newPrefSum = prefixSum[start-1] + (*sums[start] * (it-start)); } for (; start < it; start++) { prefixSum[start] = newPrefSum; } if (it < n) lastWeight = *sums[it]; } // long long sumEqual = 0; // for (; it<n; it++) { // long long s = *sums[it]; // if (s == lastWeight) { // sumEqual += s; // prefixSum[i+1] = prefixSum[i]; // } else { // prefixSum[i+1] = prefixSum[i] + sumEqual; // sumEqual = s; // } // lastWeight = s; // } // for (int i = 0; i < n; i++) { // std::cout << prefixSum[i] << " "; // } // std::cout << std::endl; // for (int i = 0; i < n; i++) { // std::cout << *sums[i] << " "; // } // std::cout << std::endl; std::vector<long long> required; required.resize(n+1); bool canEat = true; for (int i=n-1; i >= 0; i--) { long long mass = prefixSum[i]; required[i] = std::max(*sums[i], required[i+1] - *sums[i]); if (canEat && required[i+1] < mass && (i == 0 || *sums[i-1] < mass)) { *sums[i] = 1; } else { canEat = false; *sums[i] = 0; } } // for (int i = 0; i < n; i++) { // std::cout << required[i] << " "; // } // std::cout << std::endl; for (int i = 0; i < n; i++) { std::cout << (sumsOrd[i] == 1?'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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <iostream> #include <vector> #include <algorithm> const int N = 500005; long long sumsOrd[N]; long long *sums[N]; bool ptrCmp(long long *a, long long *b) { return *a < *b; } int main() { int n; std::cin >> n; for (int i=0; i<n; i++) { long long s; std::cin >> s; sumsOrd[i] = s; sums[i] = &sumsOrd[i]; } std::sort(sums, sums + n, ptrCmp); std::vector<long long> prefixSum; prefixSum.resize(n + 1); int it=0; long long lastWeight = *sums[0]; while (it < n) { int start = it; while (it < n && lastWeight == *sums[it]) {it++;} long long newPrefSum; // = prefixSum[start-1]; if (start == 0) { newPrefSum = *sums[start]; } else { newPrefSum = prefixSum[start-1] + (*sums[start] * (it-start)); } for (; start < it; start++) { prefixSum[start] = newPrefSum; } if (it < n) lastWeight = *sums[it]; } // long long sumEqual = 0; // for (; it<n; it++) { // long long s = *sums[it]; // if (s == lastWeight) { // sumEqual += s; // prefixSum[i+1] = prefixSum[i]; // } else { // prefixSum[i+1] = prefixSum[i] + sumEqual; // sumEqual = s; // } // lastWeight = s; // } // for (int i = 0; i < n; i++) { // std::cout << prefixSum[i] << " "; // } // std::cout << std::endl; // for (int i = 0; i < n; i++) { // std::cout << *sums[i] << " "; // } // std::cout << std::endl; std::vector<long long> required; required.resize(n+1); bool canEat = true; for (int i=n-1; i >= 0; i--) { long long mass = prefixSum[i]; required[i] = std::max(*sums[i], required[i+1] - *sums[i]); if (canEat && required[i+1] < mass && (i == 0 || *sums[i-1] < mass)) { *sums[i] = 1; } else { canEat = false; *sums[i] = 0; } } // for (int i = 0; i < n; i++) { // std::cout << required[i] << " "; // } // std::cout << std::endl; for (int i = 0; i < n; i++) { std::cout << (sumsOrd[i] == 1?'T':'N'); } return 0; } |