#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct ryba{ int sila; long long masa; // moc kielbasa }; bool comp(ryba a, ryba b) { return a.masa < b.masa; } vector<ryba> rybisko; vector<ryba> chaotyczne_rybisko; int n; bool karm_rybe(ryba r) { long long m = r.masa; for (int i=0;i<n;i++) { if (r.sila == rybisko[i].sila) continue; if (m > rybisko[i].masa) m += rybisko[i].masa; else return false; } return true; } ryba szukaj_ryby(int b, int e) { if (b == e) return rybisko[b]; int m = (b+e)/2; if (karm_rybe(rybisko[m])) return szukaj_ryby(b, m); else return szukaj_ryby(m+1, e); } int main() { long long t; scanf("%d", &n); for (int i=0;i<n;i++) { scanf("%lld", &t); chaotyczne_rybisko.push_back(ryba{i,t}); rybisko.push_back(ryba{i,t}); } sort(rybisko.begin(), rybisko.end(), comp); ryba r = szukaj_ryby(0, n); t = r.masa; if (karm_rybe(r)) for (int i=0;i<n;i++) { if (chaotyczne_rybisko[i].masa >= t) printf("T"); else printf("N"); } else for (int i=0;i<n;i++) {printf("N");} }
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct ryba{ int sila; long long masa; // moc kielbasa }; bool comp(ryba a, ryba b) { return a.masa < b.masa; } vector<ryba> rybisko; vector<ryba> chaotyczne_rybisko; int n; bool karm_rybe(ryba r) { long long m = r.masa; for (int i=0;i<n;i++) { if (r.sila == rybisko[i].sila) continue; if (m > rybisko[i].masa) m += rybisko[i].masa; else return false; } return true; } ryba szukaj_ryby(int b, int e) { if (b == e) return rybisko[b]; int m = (b+e)/2; if (karm_rybe(rybisko[m])) return szukaj_ryby(b, m); else return szukaj_ryby(m+1, e); } int main() { long long t; scanf("%d", &n); for (int i=0;i<n;i++) { scanf("%lld", &t); chaotyczne_rybisko.push_back(ryba{i,t}); rybisko.push_back(ryba{i,t}); } sort(rybisko.begin(), rybisko.end(), comp); ryba r = szukaj_ryby(0, n); t = r.masa; if (karm_rybe(r)) for (int i=0;i<n;i++) { if (chaotyczne_rybisko[i].masa >= t) printf("T"); else printf("N"); } else for (int i=0;i<n;i++) {printf("N");} } |