# PBinfo #4124 – colibri – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: \( \frac{(-1)^{a_i}b_i}{c_i} \)

Cerința
Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil.

Date de intrare
Fișierul de intrare colibri.in conține pe prima linie numărul N. Următoarele N linii descriu cele N triplete: pe linia i se află numerele naturale ai, bi, ci, separate prin spații.

Date de ieșire
Pe prima linie a fișierului de ieșire colibri.out se află un șir de N cifre. Cifra i, unde 1 ≤ i ≤ N, este 1 dacă și numai dacă qi este selectat în subșirul soluție, altfel este 0. Cifrele șirului nu se vor separa prin spații.

Restricții și precizări

1 ≤ N ≤ 50.000;
0 ≤ ai, bi ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;
1 ≤ ci ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;
Dacă există mai multe soluții, atunci se acceptă orice soluție corectă;
Spunem că un șir x este subșir al unui șir y dacă și numai dacă x se poate obține din y eliminând o parte din elementele lui y (inclusiv nici unul) fără a schimba ordinea relativă a elementelor rămase.
Pentru 30 de puncte, N ≤ 19 și ai, ci, ci ≤ 9
Pentru 20 de puncte, N ≤ 19
Pentru 20 de puncte, ai, bi, ci ≤ 9
Pentru 30 de puncte, fără restricții suplimentare

Exemplu:
colibri.in

5
0 0 1
2 4 2
4 7 7
1 2 3
0 3 2
colibri.out

01001
Explicație
În exemplu N=5, \( {q}_{1} = \frac{0}{1} \), \( {q}_{2} = \frac{4}{2} \), \( {q}_{3} = \frac{7}{7} \), \( {q}_{4} = -\frac{2}{3} \) și \( {q}_{5} = \frac{3}{2} \).

Produsul maxim posibil este egal cu 3. Acesta se poate obține luând fie subșirul constând din numerele q2 și q5, fie luând subșirul format din numerele q2, q3 și q5. Cu alte cuvinte, și răspunsul 01101 este corect.

## Cod sursă C++

```cpp
/* Autor: Andrei Arhire, Universitatea A.I. Cuza, Iași
 * Complexitate: O(NlogN)
 */
#include <bits/stdc++.h>
using namespace std;
struct fraction {
    int a, b, c, i;
} v[1000001];
int n;
bool cmp(fraction i, fraction j) {
    if (i.a % 2 != j.a % 2) {
        return i.a % 2 > j.a % 2;
    }
    if (i.a % 2 == 1) {
        return 1LL * i.b * j.c > 1LL * j.b * i.c;
    }
    return 1LL * i.b * j.c < 1LL * j.b * i.c;
}
signed main() {
    deque<fraction> dq;
    ifstream in("colibri.in");
    ofstream out("colibri.out");
    in >> n;
    for (int i = 1; i <= n; ++i) {
        in >> v[i].a >> v[i].b >> v[i].c;
        v[i].i = i;
    }
    sort(v + 1, v + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        dq.push_back(v[i]);
    }
    vector<fraction> sol;
    while (dq.size() > 1) {
        fraction fr1 = dq.front();
        dq.pop_front();
        fraction fr2 = dq.front();
        dq.pop_front();
        if (fr1.a % 2 == 0 || fr2.a % 2 == 0 || 1LL * fr1.b * fr2.b < 1LL * fr1.c * fr2.c) {
            dq.push_front(fr2);
            dq.push_front(fr1);
            break;
        }
        sol.emplace_back(fr1);
        sol.emplace_back(fr2);
    }
    while (!dq.empty() && dq.back().a % 2 == 0 && dq.back().b >= dq.back().c ) {
        sol.emplace_back(dq.back());
        dq.pop_back();
    }
    if (!sol.empty()) {
        string ans(n, '0');
        for (auto it : sol) {
            ans[it.i - 1] = '1';
        }
        out << ans << '\n';
        return 0;
    }
    if (dq.size() == 1) {
        out << 1 << '\n';
        return 0;
    }
    auto fr1 = dq.front();
    dq.pop_front();
    auto fr2 = dq.front();
    auto fr3 = dq.back();
    if (1LL * fr1.b * fr2.b * fr3.c > 1LL * fr3.b * fr1.c * fr1.c) {
        sol.emplace_back(fr1);
        sol.emplace_back(fr2);
    } else {
        sol.emplace_back(fr3);
    }
    string ans(n, '0');
    for (auto it : sol) {
        ans[it.i - 1] = '1';
    }
    out << ans << '\n';
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4124)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4124/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4124/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)