Submission #70992598

---

Source Code Expand

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    long long S = 0;
    for (auto x : A) S += x;

    if (S % N != 0) {
        cout << -1 << '\n';
        return 0;
    }
    long long T = S / N;

    // Collect indices that actually need changing
    vector<int> idx;          // original indices of "non-balanced" children
    vector<long long> d;      // their differences A[i] - T
    for (int i = 0; i < N; ++i) {
        if (A[i] != T) {
            idx.push_back(i);
            d.push_back(A[i] - T);
        }
    }

    int k = (int)idx.size();
    if (k == 0) {
        // Already equal
        cout << 0 << '\n';
        return 0;
    }

    int FULL = (1 << k) - 1;
    int SZ = 1 << k;

    // Precompute subset sums of d
    vector<long long> subsum(SZ, 0);
    for (int mask = 1; mask < SZ; ++mask) {
        int lsb = mask & -mask;
        int bit = __builtin_ctz(lsb);
        int prev = mask ^ lsb;
        subsum[mask] = subsum[prev] + d[bit];
    }

    const long long INF = (1LL << 60);
    vector<long long> dp(SZ, -1);
    vector<int> choose(SZ, 0);

    function<long long(int)> solve = [&](int mask) -> long long {
        if (mask == 0) return 0;
        if (dp[mask] != -1) return dp[mask];

        long long best = INF;
        int bestSub = 0;

        int lsb = mask & -mask;  // least significant bit in mask

        // Enumerate all submasks of mask that contain lsb and have zero sum
        for (int sub = mask; sub; sub = (sub - 1) & mask) {
            if (!(sub & lsb)) continue;        // must contain the fixed smallest bit
            if (subsum[sub] != 0) continue;    // group must be zero-sum

            long long costInside = __builtin_popcount(sub) - 1; // |sub|-1 ops for this group
            long long rest = solve(mask ^ sub);
            if (rest == INF) continue;
            long long cand = costInside + rest;
            if (cand < best) {
                best = cand;
                bestSub = sub;
            }
        }

        dp[mask] = best;
        choose[mask] = bestSub;
        return best;
    };

    long long minOps = solve(FULL);
    // Should always be finite because total sum is divisible by N
    // and overall sum of d[i] is zero.
    if (minOps >= INF) {
        // Defensive, but shouldn't happen:
        cout << -1 << '\n';
        return 0;
    }

    // Reconstruct groups from 'choose'
    vector<int> groups;
    int curMask = FULL;
    while (curMask) {
        int sub = choose[curMask];
        // sub must be non-zero and zero-sum by construction
        groups.push_back(sub);
        curMask ^= sub;
    }

    // Now construct operations for each group using the "star" method
    vector<tuple<int,int,long long>> ops;
    vector<long long> curA = A; // for sanity check, optional

    for (int gmask : groups) {
        // Collect positions (within idx/d arrays) belonging to this group
        vector<int> posList;
        for (int p = 0; p < k; ++p) {
            if (gmask & (1 << p)) posList.push_back(p);
        }
        if (posList.empty()) continue;

        int rootPos = posList[0];
        int rootIdx = idx[rootPos]; // original index of root child

        // First move from surplus children to root
        for (size_t t = 1; t < posList.size(); ++t) {
            int p = posList[t];
            long long diff = d[p]; // A[idx[p]] - T
            if (diff > 0) {
                int from = idx[p];
                int to   = rootIdx;
                long long z = diff;
                if (z > 0) {
                    ops.emplace_back(from, to, z);
                    curA[from] -= z;
                    curA[to]   += z;
                }
            }
        }
        // Then move from root to deficit children
        for (size_t t = 1; t < posList.size(); ++t) {
            int p = posList[t];
            long long diff = d[p];
            if (diff < 0) {
                int from = rootIdx;
                int to   = idx[p];
                long long z = -diff;
                if (z > 0) {
                    ops.emplace_back(from, to, z);
                    curA[from] -= z;
                    curA[to]   += z;
                }
            }
        }
    }

    // Sanity check (can be removed in final submission)
    // for (int i = 0; i < N; ++i) {
    //     if (curA[i] != T) {
    //         cerr << "Internal error: final candies mismatch\n";
    //         return 0;
    //     }
    // }

    // Output
    cout << (int)ops.size() << '\n';
    for (auto &op : ops) {
        int x, y;
        long long z;
        tie(x, y, z) = op;
        cout << x + 1 << ' ' << y + 1 << ' ' << z << '\n'; // convert to 1-based
    }

    return 0;
}

Submission Info

Judge Result