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

• 問題: No.3749 Three Jugs
• ユーザー: Naru820
• 提出日時: 2026-09-16 20:52:55
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,318 ms / 5,000 ms
• コード長: 5,983 bytes
• コンパイル時間: 2,685 ms
• コンパイル使用メモリ: 362,228 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-25 20:53:25
• 合計ジャッジ時間: 13,129 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_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;

    // -1: C, 0/1/2: B からの最短距離, 3: 通常の状態
    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;
    };

    // id ごとに、同じ形の辺を1グループとして持つ。
    // len[id] は本数、weight[id] はその辺1本が表す操作回数。
    vector<ll> len, weight;
    vector<int> initial;

    // order[0], order[1] はそれぞれ始点側・終点側から見た辺の並び。
    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());

        // r=0,1 で通常順・逆順の2コピーを作る。コピーを切り替えることで対応する点の順序をそろえる。
        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 -> j)--> v
            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];

            // v から後戻りしない場合の次の操作。
            // 頂点では来た辺を折り返す。
            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
            });

            // 遷移すると順序が反転するので 1-r 側へ移す。
            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]));
    }

    // 特殊状態は row[0] の先頭に集まっている。
    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();
        int b = row[1].back();

        // 両側の末尾が同じなら、その部分だけで閉じている。
        if (a == b) {
            for (auto &v : row) v.pop_back();
            continue;
        }

        // 本数の多い方を win とする。
        int side = len[a] < len[b];
        int win = row[side].back();

        auto &other = row[side ^ 1];
        auto pos = find(other.begin(), other.end(), win);

        // win より後ろを一巡処理すると、
        // 並び順は元に戻り、len[win] が sum 減る。
        ll sum = 0;
        for (auto it = pos + 1; it != other.end(); ++it)
            sum += len[*it];

        ll q = len[win] / sum;

        if (q) {
            // 同じ縮約を q 周まとめて処理する。
            len[win] %= sum;
            for (auto it = pos + 1; it != other.end(); ++it)
                weight[*it] += q * weight[win];
        } else {
            int lose = other.back();

            // s --lose--> v --win--> t を s --> t に縮約する。
            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';
    }
}