#include <algorithm> #include <iostream> using namespace std; #define N 500000 #define A 1000000000 struct num { unsigned a; unsigned cumsum; int idx; bool king; }; num nums[N + 1]; bool out[N + 1]; int main() { ios_base::sync_with_stdio(0); int n; unsigned a, mina, maxa; cin >> n; for (int i = 0; i < n; i++) { cin >> a; nums[i] = {.a = a, .idx = i, .king = false}; } sort(nums, nums + n, [](num a, num b) { return a.a < b.a; }); mina = nums[0].a; maxa = nums[n - 1].a; nums[0].cumsum = nums[0].a; for (int i = 1; i < n; i++) { nums[i].cumsum = min(maxa + 1, nums[i].a + nums[i - 1].cumsum); } nums[n - 1].king = nums[n - 1].a > mina; for (int i = n - 2; i >= 0 && nums[i + 1].king && nums[i].a > mina; i--) { nums[i].king = nums[i].cumsum > nums[i + 1].a; } for (int i = 0; i < n; i++) { out[nums[i].idx] = nums[i].king; } for (int i = 0; i < n; i++) { cout << (out[i] ? 'T' : 'N'); } cout << endl; 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 | #include <algorithm> #include <iostream> using namespace std; #define N 500000 #define A 1000000000 struct num { unsigned a; unsigned cumsum; int idx; bool king; }; num nums[N + 1]; bool out[N + 1]; int main() { ios_base::sync_with_stdio(0); int n; unsigned a, mina, maxa; cin >> n; for (int i = 0; i < n; i++) { cin >> a; nums[i] = {.a = a, .idx = i, .king = false}; } sort(nums, nums + n, [](num a, num b) { return a.a < b.a; }); mina = nums[0].a; maxa = nums[n - 1].a; nums[0].cumsum = nums[0].a; for (int i = 1; i < n; i++) { nums[i].cumsum = min(maxa + 1, nums[i].a + nums[i - 1].cumsum); } nums[n - 1].king = nums[n - 1].a > mina; for (int i = n - 2; i >= 0 && nums[i + 1].king && nums[i].a > mina; i--) { nums[i].king = nums[i].cumsum > nums[i + 1].a; } for (int i = 0; i < n; i++) { out[nums[i].idx] = nums[i].king; } for (int i = 0; i < n; i++) { cout << (out[i] ? 'T' : 'N'); } cout << endl; return 0; } |