#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; typedef long long int LL; typedef vector<LL> VL; typedef vector<VL> VVL; #define FOR(x, b, e) for(int x = b; x < (e); ++x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define EACH(x, y) for(auto &(x) : y) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define PB push_back LL solve(VL &sortedSumy) { LL maxSum = sortedSumy[SIZE(sortedSumy) - 1]; LL sumOfSums = sortedSumy[0]; LL x = 1; // Get index of first one that fits the criteria while (sumOfSums < maxSum) { sumOfSums += sortedSumy[x]; ++x; } // If number is the same with the 1st one, then find the next one that isn't (you cannot eat fish of the same size) while (sortedSumy[x - 2] == sortedSumy[x - 1]) { ++x; } return x - 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); LL n; cin >> n; VL sumy(n); REP(i, n) { cin >> sumy[i]; } VL sortedSumy = sumy; sort(ALL(sortedSumy)); LL minSum = sortedSumy[solve(sortedSumy)]; string endRes = ""; EACH(sum, sumy) { if (sum >= minSum) endRes += 'T'; else endRes += 'N'; } cout << endRes << '\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 | #include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; typedef long long int LL; typedef vector<LL> VL; typedef vector<VL> VVL; #define FOR(x, b, e) for(int x = b; x < (e); ++x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define EACH(x, y) for(auto &(x) : y) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define PB push_back LL solve(VL &sortedSumy) { LL maxSum = sortedSumy[SIZE(sortedSumy) - 1]; LL sumOfSums = sortedSumy[0]; LL x = 1; // Get index of first one that fits the criteria while (sumOfSums < maxSum) { sumOfSums += sortedSumy[x]; ++x; } // If number is the same with the 1st one, then find the next one that isn't (you cannot eat fish of the same size) while (sortedSumy[x - 2] == sortedSumy[x - 1]) { ++x; } return x - 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); LL n; cin >> n; VL sumy(n); REP(i, n) { cin >> sumy[i]; } VL sortedSumy = sumy; sort(ALL(sortedSumy)); LL minSum = sortedSumy[solve(sortedSumy)]; string endRes = ""; EACH(sum, sumy) { if (sum >= minSum) endRes += 'T'; else endRes += 'N'; } cout << endRes << '\n'; return 0; } |