Submission #70987422

---

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);
    long long S = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        S += A[i];
    }

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

    long long T = S / N;
    vector<long long> d(N);
    for (int i = 0; i < N; ++i) {
        d[i] = A[i] - T;
    }

    vector<int> pq1, pq2;
    for (int i = 0; i < N; ++i) {
        if (d[i] > 0) pq1.push_back(i);
        else if (d[i] < 0) pq2.push_back(i);
    }

    vector<tuple<int,int,long long>> ops;

    int i = 0, j = 0;
    while (i < (int)pq1.size() && j < (int)pq2.size()) {
        int x = pq1[i];
        int y = pq2[j];
        long long give = min(d[x], -d[y]);

        if (give > 0) {
            ops.emplace_back(x + 1, y + 1, give);
            d[x] -= give;
            d[y] += give;
        }

        if (d[x] == 0) ++i;
        if (d[y] == 0) ++j;
    }
    cout << ops.size() << '\n';
    for (auto &op : ops) {
        int x, y;
        long long z;
        tie(x, y, z) = op;
        cout << x << ' ' << y << ' ' << z << '\n';
    }

    return 0;
}

Submission Info

Judge Result