#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, weight;
cin>>n;
vector<bool> kings(n, false);
vector< pair<long long int, int> > weights(n);
vector< long long int > cumsums(n);
for (int i = 0; i < n; i++) {
cin>>weight;
weights.at(i) = make_pair(weight, i);
}
sort (weights.begin(),weights.end());
long long int cumsum = cumsums.at(0) = weights[0].first;
for (int i = 1 ; i < n ; i++) {
cumsum += weights[i].first;
if (weights[i-1].first < weights[i].first || cumsums[i -1] > weights[i -1].first) {
cumsums[i] = cumsum;
} else {
cumsums[i] = weights[i].first;
}
}
for (int i = n-1; i >=0; i--) {
bool isGreater = weights[i].first < cumsums[i];
if (!isGreater) break;
if (i == n-1 || weights[i+1].first < cumsums[i]) {
kings[weights[i].second] = true;
} else {
break;
}
long long int currentWeight = weights[i].first;
int k = 0;
while (i-k - 1 >= 0 && currentWeight == weights[i - k - 1].first) {
kings[weights[i - k - 1].second] = true;
k++;
}
i -= k;
}
for (int i = 0 ; i < n ; i++){
if (kings[i]) {
cout << "T";
} else {
cout << "N";
}
}
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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, weight; cin>>n; vector<bool> kings(n, false); vector< pair<long long int, int> > weights(n); vector< long long int > cumsums(n); for (int i = 0; i < n; i++) { cin>>weight; weights.at(i) = make_pair(weight, i); } sort (weights.begin(),weights.end()); long long int cumsum = cumsums.at(0) = weights[0].first; for (int i = 1 ; i < n ; i++) { cumsum += weights[i].first; if (weights[i-1].first < weights[i].first || cumsums[i -1] > weights[i -1].first) { cumsums[i] = cumsum; } else { cumsums[i] = weights[i].first; } } for (int i = n-1; i >=0; i--) { bool isGreater = weights[i].first < cumsums[i]; if (!isGreater) break; if (i == n-1 || weights[i+1].first < cumsums[i]) { kings[weights[i].second] = true; } else { break; } long long int currentWeight = weights[i].first; int k = 0; while (i-k - 1 >= 0 && currentWeight == weights[i - k - 1].first) { kings[weights[i - k - 1].second] = true; k++; } i -= k; } for (int i = 0 ; i < n ; i++){ if (kings[i]) { cout << "T"; } else { cout << "N"; } } cout<<endl; return 0; } |
English