#include <bits/stdc++.h> #define ff first #define ss second using namespace std; struct val { long long v; int idx; }; bool cmp(val a, val b) { return a.v < b.v; } int n; vector<val> ryby; bitset<500500> odp; int main() { scanf("%d", &n); ryby.resize(n); long long a, suma = 0; for (int i = 0; i < n; i++) { scanf("%lld", &a); suma += a; ryby[i] = {a, i}; } sort(ryby.begin(), ryby.end(), cmp); // Długość ciągu najmniejszych ryb int q = 0; while (q + 1 < n && ryby[q+1].v == ryby[0].v) q++; // Algorytm long long mini = 0; int p; for (p = n-1; p > q; p--) { if (suma < mini) break; odp[ryby[p].idx] = true; suma -= ryby[p].v; mini = max(ryby[p].v + 1LL, mini - ryby[p].v); } // Wypisz odpowiedź for (int i = 0; i < n; i++) { printf("%c", odp[i] ? 'T' : '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 | #include <bits/stdc++.h> #define ff first #define ss second using namespace std; struct val { long long v; int idx; }; bool cmp(val a, val b) { return a.v < b.v; } int n; vector<val> ryby; bitset<500500> odp; int main() { scanf("%d", &n); ryby.resize(n); long long a, suma = 0; for (int i = 0; i < n; i++) { scanf("%lld", &a); suma += a; ryby[i] = {a, i}; } sort(ryby.begin(), ryby.end(), cmp); // Długość ciągu najmniejszych ryb int q = 0; while (q + 1 < n && ryby[q+1].v == ryby[0].v) q++; // Algorytm long long mini = 0; int p; for (p = n-1; p > q; p--) { if (suma < mini) break; odp[ryby[p].idx] = true; suma -= ryby[p].v; mini = max(ryby[p].v + 1LL, mini - ryby[p].v); } // Wypisz odpowiedź for (int i = 0; i < n; i++) { printf("%c", odp[i] ? 'T' : 'N'); } return 0; } |