//============================================================================ // Name : 3c-sum.cpp //============================================================================ #include <iostream> #include <vector> #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); // cout << "3c-sum" << endl; // prints int n; vector<long long> fishes; cin >> n; long long a; for (int i = 0; i < n; i++) { cin >> a; fishes.push_back(a); } // for (int i = 0; i < n; i++) { // cout << fishes[i] << " "; // } // cout << endl; vector<long long> growin_fishes = fishes; sort(growin_fishes.begin(), growin_fishes.end()); // for (int i = 0; i < n; i++) { // cout << growin_fishes[i] << " "; // } // cout << endl; long long min_eating_fish1 = -1; const long long first_fish = growin_fishes[0]; for (int i = 1; i < n; i++) { if (growin_fishes[i] > first_fish) { min_eating_fish1 = growin_fishes[i]; break; } } if (min_eating_fish1 < 0) { // cout << "todo: all N" << endl; for (int i = 0; i < n; i++) { cout << "N"; } cout << endl; return 0; } // else { // cout << "min_eating_fish1 = " << min_eating_fish1 << endl; // } vector<long long> cumulated_fishes; cumulated_fishes.push_back(growin_fishes[0]); for (int i = 1; i < n; i++) { cumulated_fishes.push_back(growin_fishes[i] + cumulated_fishes[i - 1]); } // for (int i = 0; i < n; i++) { // cout << cumulated_fishes[i] << " "; // } // cout << endl; long long min_eating_fish = growin_fishes[n - 1]; for (int i = n - 2; i >= 0; i--) { if (cumulated_fishes[i] > growin_fishes[i + 1]) { min_eating_fish = growin_fishes[i]; if (min_eating_fish < min_eating_fish1) { min_eating_fish = min_eating_fish1; break; } } else { break; } } // cout << "min_eating_fish = " << min_eating_fish << endl; for (int i = 0; i < n; i++) { if (fishes[i] < min_eating_fish) { cout << "N"; } else { cout << "T"; } } 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 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 | //============================================================================ // Name : 3c-sum.cpp //============================================================================ #include <iostream> #include <vector> #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); // cout << "3c-sum" << endl; // prints int n; vector<long long> fishes; cin >> n; long long a; for (int i = 0; i < n; i++) { cin >> a; fishes.push_back(a); } // for (int i = 0; i < n; i++) { // cout << fishes[i] << " "; // } // cout << endl; vector<long long> growin_fishes = fishes; sort(growin_fishes.begin(), growin_fishes.end()); // for (int i = 0; i < n; i++) { // cout << growin_fishes[i] << " "; // } // cout << endl; long long min_eating_fish1 = -1; const long long first_fish = growin_fishes[0]; for (int i = 1; i < n; i++) { if (growin_fishes[i] > first_fish) { min_eating_fish1 = growin_fishes[i]; break; } } if (min_eating_fish1 < 0) { // cout << "todo: all N" << endl; for (int i = 0; i < n; i++) { cout << "N"; } cout << endl; return 0; } // else { // cout << "min_eating_fish1 = " << min_eating_fish1 << endl; // } vector<long long> cumulated_fishes; cumulated_fishes.push_back(growin_fishes[0]); for (int i = 1; i < n; i++) { cumulated_fishes.push_back(growin_fishes[i] + cumulated_fishes[i - 1]); } // for (int i = 0; i < n; i++) { // cout << cumulated_fishes[i] << " "; // } // cout << endl; long long min_eating_fish = growin_fishes[n - 1]; for (int i = n - 2; i >= 0; i--) { if (cumulated_fishes[i] > growin_fishes[i + 1]) { min_eating_fish = growin_fishes[i]; if (min_eating_fish < min_eating_fish1) { min_eating_fish = min_eating_fish1; break; } } else { break; } } // cout << "min_eating_fish = " << min_eating_fish << endl; for (int i = 0; i < n; i++) { if (fishes[i] < min_eating_fish) { cout << "N"; } else { cout << "T"; } } cout << endl; return 0; } |