#1170589 (C++23) No.2594 Mix shake!!

• 問題: No.2594 Mix shake!!
• ユーザー: hitonanode
• 提出日時: 2026-07-08 21:47:41
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 4,849 bytes
• コンパイル時間: 4,342 ms
• コンパイル使用メモリ: 361,576 KB
• 実行使用メモリ: 9,260 KB
• 最終ジャッジ日時: 2026-07-08 21:48:05
• 合計ジャッジ時間: 7,749 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 75 WA * 10

ソースコード

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i128 = __int128_t;

struct Vec {
    int64 a, b; // apple, banana
};

bool same_ratio(const Vec& x, const Vec& y) {
    return (i128)x.a * y.b == (i128)y.a * x.b;
}

bool less_ratio(const Vec& x, const Vec& y) {
    return (i128)x.a * y.b < (i128)y.a * x.b;
}

i128 sumA(const vector<Vec>& v) {
    i128 s = 0;
    for (auto &x : v) s += x.a;
    return s;
}

i128 sumB(const vector<Vec>& v) {
    i128 s = 0;
    for (auto &x : v) s += x.b;
    return s;
}

// t = num / den に対する Σ max(a_i - t b_i, 0) * den
i128 calc_call(const vector<Vec>& v, int64 num, int64 den) {
    i128 res = 0;
    for (auto &x : v) {
        i128 val = (i128)x.a * den - (i128)num * x.b;
        if (val > 0) res += val;
    }
    return res;
}

// src が tgt より「混ざっていない」か
bool dominates(const vector<Vec>& src, const vector<Vec>& tgt) {
    if (sumA(src) != sumA(tgt)) return false;
    if (sumB(src) != sumB(tgt)) return false;

    vector<Vec> pts;
    for (auto &x : src) pts.push_back(x);
    for (auto &x : tgt) pts.push_back(x);

    for (auto &p : pts) {
        i128 lhs = calc_call(src, p.a, p.b);
        i128 rhs = calc_call(tgt, p.a, p.b);
        if (lhs < rhs) return false;
    }
    return true;
}

pair<int64,int64> ratio_key(const Vec& x) {
    int64 g = std::gcd(x.a, x.b);
    return {x.a / g, x.b / g};
}

// 比率ごとのバナナ量の総和が同じか
bool measure_equal(const vector<Vec>& x, const vector<Vec>& y) {
    map<pair<int64,int64>, i128> mp;
    for (auto &v : x) mp[ratio_key(v)] += v.b;
    for (auto &v : y) mp[ratio_key(v)] -= v.b;
    for (auto &kv : mp) {
        if (kv.second != 0) return false;
    }
    return true;
}

bool exact_same(const vector<Vec>& x, const vector<Vec>& y) {
    int n = (int)x.size();
    for (int i = 0; i < n; i++) {
        if (x[i].a != y[i].a || x[i].b != y[i].b) return false;
    }
    return true;
}

// どれか2つを合体したあとでも tgt を作れるか
bool can_make_buffer(const vector<Vec>& src, const vector<Vec>& tgt) {
    int n = (int)src.size();

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            vector<Vec> merged;
            merged.reserve(n - 1);

            for (int k = 0; k < n; k++) {
                if (k != i && k != j) merged.push_back(src[k]);
            }

            Vec z{src[i].a + src[j].a, src[i].b + src[j].b};
            merged.push_back(z);

            if (dominates(merged, tgt)) return true;
        }
    }

    return false;
}

bool has_ratio_tie(vector<Vec> v) {
    sort(v.begin(), v.end(), [](const Vec& x, const Vec& y) {
        if (!same_ratio(x, y)) return less_ratio(x, y);
        if (x.a != y.a) return x.a < y.a;
        return x.b < y.b;
    });

    for (int i = 1; i < (int)v.size(); i++) {
        if (same_ratio(v[i - 1], v[i])) return true;
    }
    return false;
}

// 比率でソートしたラベル順の偶奇が同じか
bool even_parity_order(const vector<Vec>& src, const vector<Vec>& tgt) {
    int n = (int)src.size();

    // 同率がある場合は、同率内の順序を入れ替えられるので偶奇の障害はない
    if (has_ratio_tie(src) || has_ratio_tie(tgt)) return true;

    vector<int> os(n), ot(n);
    iota(os.begin(), os.end(), 0);
    iota(ot.begin(), ot.end(), 0);

    sort(os.begin(), os.end(), [&](int i, int j) {
        return less_ratio(src[i], src[j]);
    });

    sort(ot.begin(), ot.end(), [&](int i, int j) {
        return less_ratio(tgt[i], tgt[j]);
    });

    vector<int> pos(n);
    for (int i = 0; i < n; i++) pos[os[i]] = i;

    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = pos[ot[i]];

    int inv_parity = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i] > p[j]) inv_parity ^= 1;
        }
    }

    return inv_parity == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Vec> init(n), target(n);

    for (int i = 0; i < n; i++) cin >> init[i].a;
    for (int i = 0; i < n; i++) cin >> init[i].b;
    for (int i = 0; i < n; i++) cin >> target[i].a;
    for (int i = 0; i < n; i++) cin >> target[i].b;

    if (!dominates(init, target)) {
        cout << "No\n";
        return 0;
    }

    if (exact_same(init, target)) {
        cout << "Yes\n";
        return 0;
    }

    if (can_make_buffer(init, target)) {
        cout << "Yes\n";
        return 0;
    }

    // 比率分布が完全に同じで、バッファも作れないなら、
    // 異なる比率同士を混ぜる操作は一切できない
    if (measure_equal(init, target)) {
        cout << "No\n";
        return 0;
    }

    cout << (even_parity_order(init, target) ? "Yes" : "No") << '\n';
    return 0;
}