#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int lint; struct Catfish { int orig_pos; int mass; lint max_mass; }; void show_state(int i, int j, const vector<Catfish>& fishes) { cout << "i = " << i << ", j = " << j << endl; for (const Catfish& c: fishes) { cout << c.mass << '(' << c.max_mass << ") "; } cout << endl << "-----------------" << endl; } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; vector<Catfish> fishes(n); for (int i = 0; i < n; ++i) { int m; cin >> m; fishes[i] = {i, m, -1}; } sort(fishes.begin(), fishes.end(), [](Catfish a, Catfish b) { return a.mass < b.mass; }); vector<lint> cumsum(n); lint M = 0; for (int i = 0; i < n; ++i) { M += fishes[i].mass; cumsum[i] = M; } int j = -1; // indeks najwiekszej ryby jaka udalo sie pozrec //show_state(-1, j, fishes); for (int i = 0; i < n; ++i) { // indeks aktualnie rozpatrywanej ryby if (j >= 0) { fishes[i].max_mass = cumsum[j]; if (j < i) { fishes[i].max_mass += fishes[i].mass; } } else { fishes[i].max_mass = fishes[i].mass; } while (j + 1 < n) { if (fishes[i].max_mass > fishes[j+1].mass) { j++; if (i != j) { fishes[i].max_mass += fishes[j].mass; } } else { break; } } //show_state(i, j, fishes); } sort(fishes.begin(), fishes.end(), [](Catfish a, Catfish b) { return a.orig_pos < b.orig_pos; }); for (Catfish& c: fishes) { cout << (c.max_mass == M ? 'T' : '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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int lint; struct Catfish { int orig_pos; int mass; lint max_mass; }; void show_state(int i, int j, const vector<Catfish>& fishes) { cout << "i = " << i << ", j = " << j << endl; for (const Catfish& c: fishes) { cout << c.mass << '(' << c.max_mass << ") "; } cout << endl << "-----------------" << endl; } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; vector<Catfish> fishes(n); for (int i = 0; i < n; ++i) { int m; cin >> m; fishes[i] = {i, m, -1}; } sort(fishes.begin(), fishes.end(), [](Catfish a, Catfish b) { return a.mass < b.mass; }); vector<lint> cumsum(n); lint M = 0; for (int i = 0; i < n; ++i) { M += fishes[i].mass; cumsum[i] = M; } int j = -1; // indeks najwiekszej ryby jaka udalo sie pozrec //show_state(-1, j, fishes); for (int i = 0; i < n; ++i) { // indeks aktualnie rozpatrywanej ryby if (j >= 0) { fishes[i].max_mass = cumsum[j]; if (j < i) { fishes[i].max_mass += fishes[i].mass; } } else { fishes[i].max_mass = fishes[i].mass; } while (j + 1 < n) { if (fishes[i].max_mass > fishes[j+1].mass) { j++; if (i != j) { fishes[i].max_mass += fishes[j].mass; } } else { break; } } //show_state(i, j, fishes); } sort(fishes.begin(), fishes.end(), [](Catfish a, Catfish b) { return a.orig_pos < b.orig_pos; }); for (Catfish& c: fishes) { cout << (c.max_mass == M ? 'T' : 'N'); } cout << endl; return 0; } |