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

• 問題: No.3749 Three Jugs
• ユーザー: Naru820
• 提出日時: 2026-09-16 12:15:09
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,313 ms / 5,000 ms
• コード長: 4,212 bytes
• コンパイル時間: 2,697 ms
• コンパイル使用メモリ: 362,348 KB
• 実行使用メモリ: 9,868 KB
• 最終ジャッジ日時: 2026-09-25 20:53:12
• 合計ジャッジ時間: 13,323 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
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)

ll solve(State A, State B, State C) {
    const ll INF = 1LL << 62;
    ll W = B[0] + B[1] + B[2];
    auto boundary = [&](State x) {
        int cnt = 0;
        rep(i, 3) cnt += x[i] == 0 || x[i] == A[i];
        return cnt;
    };
    if (B == C) return 0;
    if (!boundary(C)) return -1;
    vector<State> start;
    rep(i, 3) rep(j, 3) if (i != j) {
        State x = B;
        ll d = min(x[i], A[j] - x[j]);
        x[i] -= d;
        x[j] += d;
        if (x == C) return 1;
        start.push_back(x);
    }
    if (boundary(C) >= 2) return 2;
    auto mark = [&](State x) {
        if (x == C) return -1;
        if (x == B) return 0;
        for (State y : start) if (x == y) return 1;
        return boundary(x) >= 2 ? 2 : 3;
    };

    vector<ll> len, weight;
    vector<int> initial;
    vector<array<ll, 4>> order[2];
    rep(i, 3) rep(j, 3) if (i != j) {
        int k = 3 - i - j;
        ll lo = max(0LL, W - A[i] - A[j] + 1);
        ll hi = min(A[k], W - 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, A[k], W - A[i], W - A[j], B[k], C[k]}) cut(z);
        for (State x : start) cut(x[k]);
        sort(cuts.begin(), cuts.end());
        rep(p, int(cuts.size()) - 1) rep(r, 2) {
            if (cuts[p] == cuts[p + 1]) continue;
            ll z = r ? cuts[p + 1] - 1 : cuts[p];
            int sign = 1 - 2 * r;
            State u, v;
            u[k] = v[k] = z;
            u[i] = min(A[i], W - z);
            u[j] = W - z - u[i];
            v[j] = min(A[j], W - z);
            v[i] = W - 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 = int(len.size());
            order[0].push_back({mark(u) == 3, 9 * r + 3 * i + j, sign * z, id});
            order[1].push_back({mark(v) == 3, 9 * (1 - r) + 3 * ni + nj,
                                -sign * v[3 - ni - nj], id});
            len.push_back(cuts[p + 1] - cuts[p]);
            weight.push_back(1);
            initial.push_back(mark(u));
        }
    }
    vector<int> row[2], dist;
    rep(side, 2) {
        sort(order[side].begin(), order[side].end());
        for (auto key : order[side]) row[side].push_back(int(key[3]));
    }
    for (int id : row[0]) if (initial[id] != 3) dist.push_back(initial[id]);
    while (row[0].size() > dist.size()) {
        int a = row[0].back(), b = row[1].back();
        if (a == b) {
            for (auto &v : row) v.pop_back();
            continue;
        }
        int side = len[a] < len[b];
        int win = row[side].back();
        auto &other = row[side ^ 1];
        auto pos = find(other.begin(), other.end(), win);
        ll sum = 0;
        for (auto it = pos + 1; it != other.end(); ++it) sum += len[*it];
        ll q = len[win] / sum;
        if (q) {
            len[win] %= sum;
            for (auto it = pos + 1; it != other.end(); ++it)
                weight[*it] += q * weight[win];
        } else {
            int lose = other.back();
            len[win] -= len[lose];
            weight[lose] += weight[win];
            rotate(pos + 1, other.end() - 1, other.end());
        }
        if (!len[win]) {
            row[side].pop_back();
            other.erase(pos);
        }
    }
    ll ans = INF;
    rep(i, int(dist.size())) if (dist[i] == -1) {
        int id = row[1][i];
        int p = int(find(row[0].begin(), row[0].end(), id) - row[0].begin());
        if (dist[p] >= 0) ans = min(ans, weight[id] + dist[p]);
    }
    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';
    }
}