#include <iostream> #include <stdint.h> #include <vector> #include <algorithm> using namespace std; bool czyWygra(const vector<int64_t>& sorted, uint32_t index) { uint32_t n=sorted.size(); int64_t cumsum=sorted[index]; for(uint32_t ii=0; ii<n; ii++) if (ii!=index) { if (cumsum>sorted[ii]) cumsum += sorted[ii]; else return false; } return true; } int main() { uint32_t n; cin>> n; vector<int64_t> wejscie(n); for (uint32_t ii=0; ii<n; ii++) cin>>wejscie[ii]; vector<int64_t> sorted(wejscie); sort(sorted.begin(), sorted.end()); int64_t minVal; int32_t ind1 = 0, ind2 = n-1, ind_sr; if(czyWygra(sorted, ind1)) // dla ind1=0 minVal = sorted[0]; // wszystkie ryby z listy wygrywaja else if(!czyWygra(sorted, ind2)) // dla ind1=0 minVal = sorted.back()+1; // zadna ryba z listy nie wygra else { while(ind2-ind1>1) { ind_sr = (ind1+ind2)/2; if(czyWygra(sorted, ind_sr)) ind2=ind_sr; else ind1=ind_sr; } minVal = sorted[ind2]; } for (uint32_t ii=0; ii<n; ii++) { if (wejscie[ii]<minVal) 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 | #include <iostream> #include <stdint.h> #include <vector> #include <algorithm> using namespace std; bool czyWygra(const vector<int64_t>& sorted, uint32_t index) { uint32_t n=sorted.size(); int64_t cumsum=sorted[index]; for(uint32_t ii=0; ii<n; ii++) if (ii!=index) { if (cumsum>sorted[ii]) cumsum += sorted[ii]; else return false; } return true; } int main() { uint32_t n; cin>> n; vector<int64_t> wejscie(n); for (uint32_t ii=0; ii<n; ii++) cin>>wejscie[ii]; vector<int64_t> sorted(wejscie); sort(sorted.begin(), sorted.end()); int64_t minVal; int32_t ind1 = 0, ind2 = n-1, ind_sr; if(czyWygra(sorted, ind1)) // dla ind1=0 minVal = sorted[0]; // wszystkie ryby z listy wygrywaja else if(!czyWygra(sorted, ind2)) // dla ind1=0 minVal = sorted.back()+1; // zadna ryba z listy nie wygra else { while(ind2-ind1>1) { ind_sr = (ind1+ind2)/2; if(czyWygra(sorted, ind_sr)) ind2=ind_sr; else ind1=ind_sr; } minVal = sorted[ind2]; } for (uint32_t ii=0; ii<n; ii++) { if (wejscie[ii]<minVal) cout<<'N'; else cout<<'T'; } cout<<endl; return 0; } |