#include <bits/stdc++.h> using namespace std; long long int n,a,sum; vector<long long int>pos; vector<long long int>org; long long int pocz,kon,srodek; bool czyd(long long int x) { long long int wyz=pos[x]; //cout << " x" << x << " wyz" << wyz << endl; for(int i=n-1;i>=0;i--) { if(i!=x) { if(wyz>pos[i]) wyz+=pos[i]; } } if(wyz==sum) return 1; return 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0;i<n;i++) { cin >> a; pos.push_back(a); org.push_back(a); sum+=a; } sort(pos.rbegin(),pos.rend()); // 4 / 4 4 4 4 pocz=0; kon=n-1; srodek=(pocz+kon)/2; //cout << " srodek" << srodek << endl; while(1) { //cout << pocz << " " << kon << endl; if(pocz==kon) { srodek=-1; break; } //cout << srodek << " " << czyd(srodek) << " " << czyd(srodek+1) << " pocz" << pocz << " kon" << kon << endl; if(czyd(srodek)!=czyd(srodek+1)) break; if(czyd(srodek) && czyd(srodek+1)) pocz=srodek; else kon=srodek; srodek=(pocz+kon)/2; } if(srodek==-1) { for(int i=0;i<n;i++) cout<<"N"; return 0; } for(int i=0;i<n;i++) { if(org[i]>=pos[srodek]) cout << "T"; else cout << "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 65 66 67 68 69 70 71 72 73 | #include <bits/stdc++.h> using namespace std; long long int n,a,sum; vector<long long int>pos; vector<long long int>org; long long int pocz,kon,srodek; bool czyd(long long int x) { long long int wyz=pos[x]; //cout << " x" << x << " wyz" << wyz << endl; for(int i=n-1;i>=0;i--) { if(i!=x) { if(wyz>pos[i]) wyz+=pos[i]; } } if(wyz==sum) return 1; return 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0;i<n;i++) { cin >> a; pos.push_back(a); org.push_back(a); sum+=a; } sort(pos.rbegin(),pos.rend()); // 4 / 4 4 4 4 pocz=0; kon=n-1; srodek=(pocz+kon)/2; //cout << " srodek" << srodek << endl; while(1) { //cout << pocz << " " << kon << endl; if(pocz==kon) { srodek=-1; break; } //cout << srodek << " " << czyd(srodek) << " " << czyd(srodek+1) << " pocz" << pocz << " kon" << kon << endl; if(czyd(srodek)!=czyd(srodek+1)) break; if(czyd(srodek) && czyd(srodek+1)) pocz=srodek; else kon=srodek; srodek=(pocz+kon)/2; } if(srodek==-1) { for(int i=0;i<n;i++) cout<<"N"; return 0; } for(int i=0;i<n;i++) { if(org[i]>=pos[srodek]) cout << "T"; else cout << "N"; } return 0; } |