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

• 問題: No.3749 Three Jugs
• ユーザー: Naru820
• 提出日時: 2026-09-11 00:23:46
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 511 ms / 5,000 ms
• コード長: 4,405 bytes
• コンパイル時間: 2,666 ms
• コンパイル使用メモリ: 356,700 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-25 20:51:54
• 合計ジャッジ時間: 9,001 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using State = array<ll, 3>;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(), (v).end()

ll solve(State cap, State s, State t) {
    const ll INF = 1LL << 62;
    ll water = s[0] + s[1] + s[2];
    rep(i, 3) {
        if (min(s[i], t[i]) < 0 || max(s[i], t[i]) > cap[i]) return -1;
    }
    if (water != t[0] + t[1] + t[2]) return -1;
    auto boundary = [&](State v) {
        int cnt = 0;
        rep(i, 3) cnt += v[i] == 0 || v[i] == cap[i];
        return cnt;
    };
    if (s == t) return 0;
    if (!boundary(t)) return -1;
    vector<State> start{s};
    rep(i, 3) rep(j, 3) if (i != j) {
        State v = s;
        ll d = min(v[i], cap[j] - v[j]);
        v[i] -= d;
        v[j] += d;
        if (v == t) return 1;
        start.push_back(v);
    }
    if (boundary(t) >= 2) return 2;

    array<ll, 4> order[2][300];
    ll len[300], weight[300], cost[300];
    int n = 0, keep = 0;
    rep(i, 3) rep(j, 3) if (i != j && cap[i] && cap[j]) {
        int k = 3 - i - j;
        ll lo = max(0LL, water - cap[i] - cap[j] + 1);
        ll hi = min(cap[k], water - 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);
            }
        };
        for (ll z : {0LL, cap[k], water - cap[i], water - cap[j]}) cut(z);
        for (State v : start) if (v[i] == cap[i] || v[j] == 0) cut(v[k]);
        if (t[i] == 0 || t[i] == cap[i] || t[j] == 0 || t[j] == cap[j]) cut(t[k]);
        sort(all(cuts));
        for (int p = 1; p < (int)cuts.size(); ++p) rep(rev, 2) {
            if (cuts[p] == cuts[p - 1]) continue;
            int sign = 1 - 2 * rev;
            ll z = rev ? cuts[p] - 1 : cuts[p - 1];
            State u, v;
            u[k] = v[k] = z;
            u[i] = min(cap[i], water - z);
            u[j] = water - z - u[i];
            v[j] = min(cap[j], water - z);
            v[i] = water - z - v[j];
            int ni = j, nj = i;
            if (boundary(v) == 1) {
                ni = v[i] == 0 ? k : j;
                nj = v[i] == 0 ? i : k;
            }
            int id = n++;
            order[0][id] = {u != t, 3 * i + j + 9 * rev, sign * z, id};
            order[1][id] = {v != t, 3 * ni + nj + 9 * (1 - rev),
                           -sign * v[3 - ni - nj], id};
            len[id] = cuts[p] - cuts[p - 1];
            weight[id] = 1;
            ll best = boundary(u) >= 2 ? 2 : INF;
            rep(h, (int)start.size()) if (u == start[h]) best = min(best, ll(h != 0));
            cost[id] = best;
            keep += u == t;
        }
    }
    vector<int> row[2];
    rep(side, 2) {
        sort(order[side], order[side] + n);
        row[side].reserve(n);
        rep(h, n) row[side].push_back(order[side][h][3]);
    }
    while ((int)row[0].size() > keep) {
        int win = row[0].back(), lose = row[1].back();
        if (win == lose) {
            for (auto &r : row) r.pop_back();
            continue;
        }
        int side = len[win] < len[lose];
        win = row[side].back();
        auto &other = row[side ^ 1];
        auto first = other.end(), last = first;
        ll sum = 0;
        while (*(first - 1) != win) sum += len[*--first];
        ll q = len[win] / sum;
        len[win] %= sum;
        auto mid = last;
        while (mid != first && len[win] >= len[*(mid - 1)]) len[win] -= len[*--mid];
        for (auto it = q ? first : mid; it != last; ++it) {
            ll rounds = q + (it >= mid);
            lose = *it;
            cost[lose] = side ? min(cost[win], rounds * weight[win] + cost[lose])
                              : min(cost[lose], weight[lose] + cost[win]);
            weight[lose] += rounds * weight[win];
        }
        rotate(first, mid, last);
        if (!len[win]) {
            row[side].pop_back();
            other.erase(first - 1);
        }
    }
    ll ans = INF;
    for (int id : row[0]) ans = min(ans, cost[id]);
    return ans == INF ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        State A, B, C;
        for (ll &x : A) cin >> x;
        for (ll &x : B) cin >> x;
        for (ll &x : C) cin >> x;
        cout << solve(A, B, C) << '\n';
    }
}