#1190071 (C++23) No.3749 Three Jugs

• 問題: No.3749 Three Jugs
• ユーザー: ponjuice
• 提出日時: 2026-09-22 00:14:54
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 624 ms / 5,000 ms
• コード長: 5,024 bytes
• コンパイル時間: 2,664 ms
• コンパイル使用メモリ: 361,940 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-25 20:56:41
• 合計ジャッジ時間: 10,257 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 23

ソースコード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(ll i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
const ll INF = 1LL<<62;

array<ll,3> a,b,c;

array<ll,3> op(array<ll,3> x, int i, int j) {
    ll mn = min(x[i], a[j] - x[j]);
    x[i] -= mn;
    x[j] += mn;
    return x;
}

void solve() {
    rep(i,0,3) cin >> a[i];
    rep(i,0,3) cin >> b[i];
    rep(i,0,3) cin >> c[i];
    ll sum = b[0] + b[1] + b[2];

    if(b == c) {
        cout << 0 << endl;
        return;
    }

    auto boundary = [&](array<ll,3> x) {
        int cnt = 0;
        rep(i,0,3) cnt += (x[i] == 0 || x[i] == a[i]);
        return cnt;
    };
    if(boundary(c) == 0) {
        cout << -1 << endl;
        return;
    }

    vector<array<ll,3>> start = {b};
    rep(i,0,3) rep(j,0,3) if(i != j) start.push_back(op(b, i, j));

    for(auto x: start) if(x == c) {
        cout << 1 << endl;
        return;
    }
    if(boundary(c) >= 2) {
        cout << 2 << endl;
        return;
    }

    ll n = 0;
    ll keep = 0;
    vector<ll> length, weight, cost;
    vector<vector<array<ll,4>>> order(2);
    rep(i,0,3) {
        rep(j,0,3) {
            if(i == j || a[i] == 0 || a[j] == 0) continue;
            int k = 3 - i - j;
            ll lo = max(0LL, sum - a[i] - a[j] + 1);
            ll hi = min(a[k], sum - 1);

            if(lo > hi) continue;

            vector<ll> cuts{lo, hi + 1};
            auto cut = [&](ll z) {
                if(lo <= z && z <= hi) {
                    cuts.push_back(z);
                    cuts.push_back(z + 1);
                }
            };
            cut(0LL); 
            cut(a[k]); 
            cut(sum - a[i]); 
            cut(sum - a[j]);
            for(auto v : start) if(v[i] == a[i] || v[j] == 0) cut(v[k]);
            if(c[i] == 0 || c[i] == a[i] || c[j] == 0 || c[j] == a[j]) cut(c[k]);

            sort(all(cuts));

            rep(p,1,cuts.size()) {
                rep(rev,0,2) {
                    if(cuts[p] == cuts[p - 1]) continue;
                    ll sign = 1 - 2 * rev;
                    ll z = rev ? cuts[p] - 1 : cuts[p - 1];
                    array<ll,3> u, v;
                    u[k] = v[k] = z;

                    u[i] = min(a[i], sum - z);
                    u[j] = sum - z - u[i];
                    v[j] = min(a[j], sum - z);
                    v[i] = sum - z - v[j];

                    int ni = j, nj = i;
                    if(boundary(v) == 1) {
                        if(v[i] == 0) ni = k, nj = i;
                        else ni = j, nj = k;
                    }

                    ll idx = n++;
                    order[0].push_back({u != c, 3 * i + j + 9 * rev, sign * z, idx});
                    order[1].push_back({v != c, 3 * ni + nj + 9 * (1 - rev), -sign * v[3 - ni - nj], idx});
                    length.push_back(cuts[p] - cuts[p - 1]);
                    weight.push_back(1);

                    ll best = boundary(u) >= 2 ? 2 : INF;
                    rep(h,0,start.size()) {
                        if(u == start[h]) {
                            best = min(best, ll(h != 0 ? 1: 0));
                        }
                    }
                    cost.push_back(best);
                    if(u == c) keep++;
                }
            }
        }
    }

    vector<vector<ll>> row(2);
    rep(side,0,2) {
        sort(all(order[side]));
        for(auto x : order[side]) row[side].push_back(x[3]);
    }

    while(row[0].size() > keep) {
        ll win = row[0].back(), lose = row[1].back();
        if(win == lose) {
            row[0].pop_back();
            row[1].pop_back();
            continue;
        }

        int side = (length[win] < length[lose]);
        win = row[side].back();
        ll first = row[side^1].size(), total = 0;
        while(row[side^1][first - 1] != win) {
            first--;
            total += length[row[side^1][first]];
        }
        ll last = row[side^1].size();

        ll q = length[win] / total;
        length[win] %= total;
        ll mid = last;
        while(mid != first && length[win] >= length[row[side^1][mid - 1]]) {
            mid--;
            length[win] -= length[row[side^1][mid]];
        }

        ll begin = q ? first : mid;
        rep(pos, begin, last) {
            ll rounds = q + (pos >= mid? 1: 0);
            lose = row[side^1][pos];
            if(side) cost[lose] = min(cost[win], rounds * weight[win] + cost[lose]);
            else cost[lose] = min(cost[lose], weight[lose] + cost[win]);
            weight[lose] += rounds * weight[win];
        }

        rotate(row[side^1].begin() + first, row[side^1].begin() + mid, row[side^1].begin() + last);
        if(length[win] == 0) {
            row[side].pop_back();
            row[side^1].erase(row[side^1].begin() + first - 1);
        }
    }

    ll ans = INF;
    for(ll idx : row[0]) ans = min(ans, cost[idx]);
    cout << (ans == INF ? -1 : ans) << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}