#define ull unsigned long long
#include <bits/stdc++.h>
using namespace std;
int main(){
ull n, leftsum = 0;
cin >> n;
vector <pair<ull, ull>> arr;
bool canWin[n] = {0};
for(int i = 0; i < n; i++){
ull a;
cin >> a;
arr.push_back(make_pair(a, i));
canWin[i] = 0;
}
if(n == 1){
cout << "T\n";
return 0;
}
sort(arr.begin(), arr.begin() + n);
reverse(arr.begin(), arr.begin() + n);
if(arr[0].first == arr[n - 1].first){
for(int i = 0; i < n; i++){
cout << "N";
}
cout << endl;
return 0;
}
canWin[arr[0].second] = 1;
ull rightsum[n] = {0};
rightsum[n - 1] = arr[n - 1].first;
for(int i = n - 2; i >= 0; i--){
rightsum[i] = rightsum[i + 1] + arr[i].first;
}
//for(int i = 0; i < n; i++){
// cout << arr[i].first << " " << rightsum[i] << endl;
//}
bool minWinFound = 0;
for(int i = 1; i < n; i++){
if(minWinFound){
continue;
}
if(rightsum[i] > arr[i - 1].first && arr[i].first != arr[n - 1]. first){
canWin[arr[i].second] = 1;
}else{
minWinFound = 1;
}
}
for(int i = 0; i < n; i++){
if(canWin[i]){
cout << "T";
}else{
cout << "N";
}
}
cout << endl;
}
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 | #define ull unsigned long long #include <bits/stdc++.h> using namespace std; int main(){ ull n, leftsum = 0; cin >> n; vector <pair<ull, ull>> arr; bool canWin[n] = {0}; for(int i = 0; i < n; i++){ ull a; cin >> a; arr.push_back(make_pair(a, i)); canWin[i] = 0; } if(n == 1){ cout << "T\n"; return 0; } sort(arr.begin(), arr.begin() + n); reverse(arr.begin(), arr.begin() + n); if(arr[0].first == arr[n - 1].first){ for(int i = 0; i < n; i++){ cout << "N"; } cout << endl; return 0; } canWin[arr[0].second] = 1; ull rightsum[n] = {0}; rightsum[n - 1] = arr[n - 1].first; for(int i = n - 2; i >= 0; i--){ rightsum[i] = rightsum[i + 1] + arr[i].first; } //for(int i = 0; i < n; i++){ // cout << arr[i].first << " " << rightsum[i] << endl; //} bool minWinFound = 0; for(int i = 1; i < n; i++){ if(minWinFound){ continue; } if(rightsum[i] > arr[i - 1].first && arr[i].first != arr[n - 1]. first){ canWin[arr[i].second] = 1; }else{ minWinFound = 1; } } for(int i = 0; i < n; i++){ if(canWin[i]){ cout << "T"; }else{ cout << "N"; } } cout << endl; } |
English