#include <iostream> #include <vector> #include <algorithm> bool can_become_king(const std::vector<std::pair<int, int>> &sumy, int index) { int rozmiar = sumy[index].first; int max = sumy[sumy.size() - 1].first; for (int i = 0; i < index; ++i) { if (sumy[i].first < rozmiar) { rozmiar += sumy[i].first; if (rozmiar > max) { break; } } } for (int i = index + 1; i < sumy.size(); ++i) { if (sumy[i].first < rozmiar) { rozmiar += sumy[i].first; if (rozmiar > max) { break; } } } return rozmiar > max; } void solution() { int n; std::cin >> n; std::vector<std::pair<int, int>> sumy(n); int tmp; for (int i = 0; i < n; ++i) { std::cin >> tmp; sumy[i] = std::pair<int, int>(tmp, i); } if (n == 1) { std::cout << "T\n"; return; } std::sort(sumy.begin(), sumy.end()); int start = 0; int end = n - 1; int middle; bool can = false; while (start < end) { middle = (end - start) / 2 + start; if (can_become_king(sumy, middle)) { can = true; end = middle; } else { start = middle + 1; } } if (!can && can_become_king(sumy, n - 1)) { can = true; start = n - 1; end = n - 1; } // da sie if (can) { std::vector<bool> can_be(n, false); for (int i = start; i < sumy.size(); ++i) { can_be[sumy[i].second] = true; } for (int i = 0; i < sumy.size(); ++i) { if (can_be[i]) { std::cout << 'T'; } else { std::cout << 'N'; } } std::cout << "\n"; } // nie da sie else { for (int i = 0; i < sumy.size(); ++i) { std::cout << 'N'; } std::cout << "\n"; } } int main() { solution(); 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 | #include <iostream> #include <vector> #include <algorithm> bool can_become_king(const std::vector<std::pair<int, int>> &sumy, int index) { int rozmiar = sumy[index].first; int max = sumy[sumy.size() - 1].first; for (int i = 0; i < index; ++i) { if (sumy[i].first < rozmiar) { rozmiar += sumy[i].first; if (rozmiar > max) { break; } } } for (int i = index + 1; i < sumy.size(); ++i) { if (sumy[i].first < rozmiar) { rozmiar += sumy[i].first; if (rozmiar > max) { break; } } } return rozmiar > max; } void solution() { int n; std::cin >> n; std::vector<std::pair<int, int>> sumy(n); int tmp; for (int i = 0; i < n; ++i) { std::cin >> tmp; sumy[i] = std::pair<int, int>(tmp, i); } if (n == 1) { std::cout << "T\n"; return; } std::sort(sumy.begin(), sumy.end()); int start = 0; int end = n - 1; int middle; bool can = false; while (start < end) { middle = (end - start) / 2 + start; if (can_become_king(sumy, middle)) { can = true; end = middle; } else { start = middle + 1; } } if (!can && can_become_king(sumy, n - 1)) { can = true; start = n - 1; end = n - 1; } // da sie if (can) { std::vector<bool> can_be(n, false); for (int i = start; i < sumy.size(); ++i) { can_be[sumy[i].second] = true; } for (int i = 0; i < sumy.size(); ++i) { if (can_be[i]) { std::cout << 'T'; } else { std::cout << 'N'; } } std::cout << "\n"; } // nie da sie else { for (int i = 0; i < sumy.size(); ++i) { std::cout << 'N'; } std::cout << "\n"; } } int main() { solution(); return 0; } |