#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; } |