#include <cstdio> #include <vector> #include <algorithm> #include <cstdlib> // #define DEBUG_M #ifdef DEBUG_M #define DEBUGF(...) fprintf(stderr, __VA_ARGS__) #define DEBUG(expr) expr #else #define DEBUGF(...) #define DEBUG(expr) #endif using namespace std; typedef int64_t i64; struct fish { i64 value; i64 prefix; }; i64 minElem; // GLOBAL bool operator<(const fish& a, const fish& b) { return (a.value != b.value) ? a.value < b.value : a.prefix < b.prefix; } bool is_possible(i64 size, const vector<fish> &fishes /* 100% valid english :) */) { i64 maxSize = fishes[fishes.size()-2].prefix; DEBUGF("initial size: %d; minElem: %d;\n", (int) size, (int) minElem); if (size++ == minElem) { return false; } for (;size < maxSize;) { fish fakeFish = {size, -1}; auto newSizeIter = lower_bound(fishes.begin(), fishes.end(), fakeFish); newSizeIter--; i64 newSize = newSizeIter -> prefix; DEBUGF("new size: %d\n", (int) newSize); if (newSize >= maxSize) { DEBUGF("returning true\n"); return true; } else if (newSize == size) { // Nothing changed DEBUGF("returning false\n"); return false; } else { // newSize > size size = newSize; } } return true; // Should never happen as well } bool is_possible_linear(int idx, const vector<fish> &fishes /* 100% valid english :) */) { DEBUGF("initial idx: %d; initial val: %d;\n", idx, (int) fishes[idx].value); if (fishes[idx].value == minElem) { return false; } for (int i = idx+1; i < fishes.size()-1; i++) { if (fishes[i-1].prefix <= fishes[i].value) return false; } return true; } int main() { int n; scanf(" %d", &n); std::vector<int> inFish(n); std::vector<fish> sortFish(n+1, {0,0}); for (int i = 0; i < n; i++) { scanf(" %d", &inFish[i]); sortFish[i].value = inFish[i]; } if (n == 1) { puts("T"); return 0; } sortFish[n] = {1000000001, 1LL << 48}; std::sort(sortFish.begin(), sortFish.end()); minElem = sortFish[0].value; sortFish[0].prefix = sortFish[0].value; for (int i = 1; i < n; i++) { sortFish[i].prefix = sortFish[i-1].prefix + sortFish[i].value; } int down = 0; int up = n+1; /* int lastDown = 0; int lastUp = 0; bool lastDownRes = false; bool lastUpRes = false; */ for (;down < up;) { int mid = (down+up)/2; // int val = sortFish[mid].value; bool res; /* if (lastDown == val) { res = lastRes; } else if (lastUp == val) { } else { */ // res = is_possible(val, sortFish); res = is_possible_linear(mid, sortFish); if (res) { up = mid; } else { down = mid + 1; } // lastVal = val; // lastRes = res; } int limit = (int) sortFish[down].value; DEBUGF("down: %d; val[down]: %d;\n", down, (int) sortFish[down].value); for (int weight : inFish) { putchar(weight >= limit ? 'T': 'N'); } puts(""); }
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 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | #include <cstdio> #include <vector> #include <algorithm> #include <cstdlib> // #define DEBUG_M #ifdef DEBUG_M #define DEBUGF(...) fprintf(stderr, __VA_ARGS__) #define DEBUG(expr) expr #else #define DEBUGF(...) #define DEBUG(expr) #endif using namespace std; typedef int64_t i64; struct fish { i64 value; i64 prefix; }; i64 minElem; // GLOBAL bool operator<(const fish& a, const fish& b) { return (a.value != b.value) ? a.value < b.value : a.prefix < b.prefix; } bool is_possible(i64 size, const vector<fish> &fishes /* 100% valid english :) */) { i64 maxSize = fishes[fishes.size()-2].prefix; DEBUGF("initial size: %d; minElem: %d;\n", (int) size, (int) minElem); if (size++ == minElem) { return false; } for (;size < maxSize;) { fish fakeFish = {size, -1}; auto newSizeIter = lower_bound(fishes.begin(), fishes.end(), fakeFish); newSizeIter--; i64 newSize = newSizeIter -> prefix; DEBUGF("new size: %d\n", (int) newSize); if (newSize >= maxSize) { DEBUGF("returning true\n"); return true; } else if (newSize == size) { // Nothing changed DEBUGF("returning false\n"); return false; } else { // newSize > size size = newSize; } } return true; // Should never happen as well } bool is_possible_linear(int idx, const vector<fish> &fishes /* 100% valid english :) */) { DEBUGF("initial idx: %d; initial val: %d;\n", idx, (int) fishes[idx].value); if (fishes[idx].value == minElem) { return false; } for (int i = idx+1; i < fishes.size()-1; i++) { if (fishes[i-1].prefix <= fishes[i].value) return false; } return true; } int main() { int n; scanf(" %d", &n); std::vector<int> inFish(n); std::vector<fish> sortFish(n+1, {0,0}); for (int i = 0; i < n; i++) { scanf(" %d", &inFish[i]); sortFish[i].value = inFish[i]; } if (n == 1) { puts("T"); return 0; } sortFish[n] = {1000000001, 1LL << 48}; std::sort(sortFish.begin(), sortFish.end()); minElem = sortFish[0].value; sortFish[0].prefix = sortFish[0].value; for (int i = 1; i < n; i++) { sortFish[i].prefix = sortFish[i-1].prefix + sortFish[i].value; } int down = 0; int up = n+1; /* int lastDown = 0; int lastUp = 0; bool lastDownRes = false; bool lastUpRes = false; */ for (;down < up;) { int mid = (down+up)/2; // int val = sortFish[mid].value; bool res; /* if (lastDown == val) { res = lastRes; } else if (lastUp == val) { } else { */ // res = is_possible(val, sortFish); res = is_possible_linear(mid, sortFish); if (res) { up = mid; } else { down = mid + 1; } // lastVal = val; // lastRes = res; } int limit = (int) sortFish[down].value; DEBUGF("down: %d; val[down]: %d;\n", down, (int) sortFish[down].value); for (int weight : inFish) { putchar(weight >= limit ? 'T': 'N'); } puts(""); } |