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

• 問題: No.3749 Three Jugs
• ユーザー: Naru820
• 提出日時: 2026-09-11 00:24:14
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,275 ms / 5,000 ms
• コード長: 6,392 bytes
• コンパイル時間: 3,177 ms
• コンパイル使用メモリ: 361,900 KB
• 実行使用メモリ: 9,848 KB
• 最終ジャッジ日時: 2026-09-25 20:52:08
• 合計ジャッジ時間: 14,129 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

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

ソースコード

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

using ll = long long;
using State = array<ll, 3>;

ll solve(State A, State B, State C) {
    const ll INF = 1LL << 62;
    ll W = B[0] + B[1] + B[2];
    for (int i = 0; i < 3; ++i) {
        if (min(B[i], C[i]) < 0 || max(B[i], C[i]) > A[i]) return -1;
    }
    if (W != C[0] + C[1] + C[2]) return -1;

    auto boundary = [&](State x) {
        int count = 0;
        for (int i = 0; i < 3; ++i) {
            count += (x[i] == 0 || x[i] == A[i]);
        }
        return count;
    };

    // Initial state and all states reachable in one operation.
    map<State, ll> dist;
    dist[B] = 0;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (i == j) continue;
            State x = B;
            ll amount = min(x[i], A[j] - x[j]);
            x[i] -= amount;
            x[j] += amount;
            if (!dist.count(x)) dist[x] = 1;
        }
    }
    if (dist.count(C)) return dist[C];
    if (boundary(C) == 0) return -1;
    if (A[0] == 0 || A[1] == 0 || A[2] == 0) return -1;

    vector<ll> length, weight, cost;
    vector<array<ll, 4>> order[2];
    int keep = 0;

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (i == j) continue;
            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;

            for (int r = 0; r < 2; ++r) {
                int sign = (r == 0 ? 1 : -1);
                vector<ll> cuts;
                if (r == 0) {
                    cuts = {lo, hi + 1};
                } else {
                    cuts = {-hi, 1 - lo};
                }

                // Split at every value listed in the editorial.
                vector<ll> points = {0, A[k], W - A[i], W - A[j], C[k]};
                for (auto [x, d] : dist) points.push_back(x[k]);
                for (ll z : points) {
                    if (lo <= z && z <= hi) {
                        cuts.push_back(sign * z);
                        cuts.push_back(sign * z + 1);
                    }
                }
                sort(cuts.begin(), cuts.end());
                cuts.erase(unique(cuts.begin(), cuts.end()), cuts.end());

                for (int p = 0; p + 1 < (int)cuts.size(); ++p) {
                    ll z = sign * cuts[p];
                    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 next_i, next_j;
                    if (boundary(v) >= 2) {
                        next_i = j;
                        next_j = i;
                    } else if (W - z < A[j]) {
                        next_i = k;
                        next_j = i;
                    } else {
                        next_i = j;
                        next_j = k;
                    }
                    int next_k = 3 - next_i - next_j;

                    int id = length.size();
                    // Keys: non-target flag, chart, coordinate, label.
                    order[0].push_back({u != C, 9 * r + 3 * i + j,
                                        cuts[p], id});
                    order[1].push_back({v != C, 9 * (1 - r) + 3 * next_i + next_j,
                                        -sign * v[next_k], id});
                    length.push_back(cuts[p + 1] - cuts[p]);
                    weight.push_back(1);

                    ll d = INF;
                    if (dist.count(u)) {
                        d = dist[u];
                    } else if (boundary(u) >= 2) {
                        d = 2;
                    }
                    cost.push_back(d);
                    if (u == C) ++keep;
                }
            }
        }
    }

    // Keep the target copies at the beginning of both rows.
    vector<int> row[2];
    for (int side = 0; side < 2; ++side) {
        sort(order[side].begin(), order[side].end());
        for (auto key : order[side]) row[side].push_back(key[3]);
    }

    while ((int)row[0].size() > keep) {
        int top = row[0].back();
        int bottom = row[1].back();
        if (top == bottom) {
            row[0].pop_back();
            row[1].pop_back();
            continue;
        }

        int side = (length[top] < length[bottom] ? 1 : 0);
        int winner = row[side].back();
        auto &other = row[1 - side];
        int pos = find(other.begin(), other.end(), winner) - other.begin();
        ll S = 0;
        for (int p = pos + 1; p < (int)other.size(); ++p) {
            S += length[other[p]];
        }

        ll q = length[winner] / S;
        if (q > 0) {
            // q full cycles: the row order returns to its original order.
            length[winner] -= q * S;
            for (int p = pos + 1; p < (int)other.size(); ++p) {
                int loser = other[p];
                if (side == 0) {
                    cost[loser] = min(cost[loser], weight[loser] + cost[winner]);
                } else {
                    cost[loser] = min(cost[winner], q * weight[winner] + cost[loser]);
                }
                weight[loser] += q * weight[winner];
            }
        } else {
            // One ordinary contraction.
            int loser = other.back();
            length[winner] -= length[loser];
            if (side == 0) {
                cost[loser] = min(cost[loser], weight[loser] + cost[winner]);
            } else {
                cost[loser] = min(cost[winner], weight[winner] + cost[loser]);
            }
            weight[loser] += weight[winner];
            other.pop_back();
            other.insert(other.begin() + pos + 1, loser);
        }

        if (length[winner] == 0) {
            for (int s = 0; s < 2; ++s) {
                row[s].erase(find(row[s].begin(), row[s].end(), winner));
            }
        }
    }

    ll answer = INF;
    for (int id : row[0]) answer = min(answer, cost[id]);
    return answer == INF ? -1 : answer;
}

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';
    }
}