Submission #685178

#	Time	Username	Problem	Language	Result	Execution time	Memory
685178		stanislavpolyn	Mixture (BOI20_mixture)	C++17	0 / 100	2 ms	212 KiB

Mixture

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}
template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 2e5 + 5;

const ld EPS = 1e-10;

bool eq(ld a, ld b) {
    return abs(a - b) <= EPS;
}

array<int, 3> a;
ve<array<int, 3>> all;
bool del[N];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//
//        cout << ld(x) / (x + y + z) << " " << ld(y) / (x + y + z) << " " << ld(z) / (x + y + z) << "\n";
//
//        int x2, y2, z2;
//        cin >> x2 >> y2 >> z2;
//        cout << ld(x2) / (x2 + y2 + z2) << " " << ld(y2) / (x2 + y2 + z2) << " " << ld(z2) / (x2 + y2 + z2) << "\n";
//
//        for (ld take = 0; take <= 1; take += 0.01) {
//            ld X = 0, Y = 0, Z = 0;
//            X += take * (ld(x) / (x + y + z));
//            Y += take * (ld(y) / (x + y + z));
//            Z += take * (ld(z) / (x + y + z));
//
//            X += (1.0 - take) * (ld(x2) / (x2 + y2 + z2));
//            Y += (1.0 - take) * (ld(y2) / (x2 + y2 + z2));
//            Z += (1.0 - take) * (ld(z2) / (x2 + y2 + z2));
//
//
//            cout << ld(X) / ld(X + Y + Z) << " " << ld(Y) / ld(X + Y + Z) << " " << ld(Z) / ld(X + Y + Z) << "\n";
//        }
//     }
//
//    return 0;

    fr (i, 0, 2) cin >> a[i];
    int g = __gcd(__gcd(a[0], a[1]), a[2]);
    if (g) {
        fr (i, 0, 2) a[i] /= g;
    }

    int q;
    cin >> q;

    fr (i, 1, q) {
        char c;
        cin >> c;

        if (c == 'A') {
            int x, y, z;
            cin >> x >> y >> z;
            int g = __gcd(__gcd(x, y), z);
            if (g) {
                x /= g;
                y /= g;
                z /= g;
            }
            all.pb({x, y, z});
        } else {
            int idx;
            cin >> idx;
            del[idx - 1] = 1;
        }

        bool found = 0;
        fr (p, 0, sz(all) - 1) {
            if (del[p]) continue;
            if (all[p] == a) {
                cout << "1\n";
                found = 1;
                break;
            }
        }
        if (found) {
            continue;
        }

        fr (p1, 0, sz(all) - 1) {
            if (del[p1]) continue;
            fr (p2, 0, sz(all) - 1) {
                if (p1 == p2) continue;
                if (del[p2]) continue;

                bool ok = 1;
                ld X1 = all[p1][0] / ld(all[p1][0] + all[p1][1] + all[p1][2]);
                ld Y1 = all[p1][1] / ld(all[p1][0] + all[p1][1] + all[p1][2]);
                ld Z1 = all[p1][2] / ld(all[p1][0] + all[p1][1] + all[p1][2]);
                ld X2 = all[p2][0] / ld(all[p2][0] + all[p2][1] + all[p2][2]);
                ld Y2 = all[p2][1] / ld(all[p2][0] + all[p2][1] + all[p2][2]);
                ld Z2 = all[p2][2] / ld(all[p2][0] + all[p2][1] + all[p2][2]);

                ld X = a[0] / ld(a[0] + a[1] + a[2]);
                ld Y = a[1] / ld(a[0] + a[1] + a[2]);
                ld Z = a[2] / ld(a[0] + a[1] + a[2]);

                if (!(X1 <= X && X <= X2)) continue;

//                cout << X << " " << Y << " " << Z << "\n";
//                cout << X1 << " " << Y1 << " " << Z1 << "\n";
//                cout << X2 << " " << Y2 << " " << Z2 << "\n\n";

                ld L = 0;
                ld R = 1;
                fr (rep, 1, 100) {
                    ld mid = (L + R) / 2.0;

                    ld t = 0;
                    t += mid * X1;
                    t += (1.0 - mid) * X2;

//                    cout << "mid, t: " << mid << " " << t << "\n";

                    if (t > X) {
                        L = mid;
                    } else {
                        R = mid;
                    }
                }
//                cout << L * X1 + (1.0 - L) * X2 << " " << X << "\n";

                {
                    ld take = L;
                    ld x = 0, y = 0, z = 0;
                    x += take * X1;
                    y += take * Y1;
                    z += take * Z1;

                    x += (1.0 - take) * X2;
                    y += (1.0 - take) * Y2;
                    z += (1.0 - take) * Z2;
                    assert(eq(x, X));

                    assert(eq(x + y + z, 1.0));

                    ok &= eq(x, X);
                    ok &= eq(y, Y);
                    ok &= eq(z, Z);
                }

                if (ok) {
                    cout << "2\n";
                    found = 1;
                    break;
                }
            }
            if (found) {
                break;
            }
        }


        if (!found) {
            cout << "0\n";
        }
    }



    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40