Submission #74962504

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<
    T,                                 // key type
    null_type,                         // mapped type (null for set)
    less<T>,                           // ordering
    rb_tree_tag,                       // underlying tree
    tree_order_statistics_node_update> // enable order-statistics
    ;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<string> vs;

template <typename T>
void debug(const vector<T> &x)
{
    for (const auto &elem : x)
    {
        cout << elem << ' ';
    }
    cout << endl;
}

// =================== CONSTANTS ====================
const ll MOD = 1000000007;
const ll mod9 = 998244353;
const ll INF = numeric_limits<int>::max();

// =================== MACROS ======================
#define fast_cin()                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define fr(i, a, b) for (ll i = (a); i < (b); ++i)
#define fo(i, n) for (ll i = (0); i < (n); ++i)
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

// ================= QUERY FUNCTION =================
ll query(ll a, ll b)
{
    cout << "? " << a << " " << b << endl;
    cout.flush();
    ll x;
    cin >> x;
    return x;
}

// ================= SEGMENT TREE ===================
struct SegmentTree
{
    vector<ll> tree;
    int n;

    SegmentTree(int size)
    {
        n = size;
        tree.assign(4 * n, 0); // Change 0 to INF for min, -INF for max
    }

    SegmentTree(const vector<ll> &arr)
    {
        n = arr.size();
        tree.assign(4 * n, 0);
        build(0, 0, n - 1, arr);
    }

    void build(int node, int start, int end, const vector<ll> &arr)
    {
        if (start == end)
        {
            tree[node] = arr[start];
        }
        else
        {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid, arr);
            build(2 * node + 2, mid + 1, end, arr);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    ll query(int node, int start, int end, int l, int r)
    {
        if (r < start || end < l)
            return 0;
        if (l <= start && end <= r)
            return tree[node];
        int mid = (start + end) / 2;
        return query(2 * node + 1, start, mid, l, r) + query(2 * node + 2, mid + 1, end, l, r);
    }

    void update(int node, int start, int end, int idx, ll val)
    {
        if (start == end)
        {
            tree[node] = val;
        }
        else
        {
            int mid = (start + end) / 2;
            if (idx <= mid)
                update(2 * node + 1, start, mid, idx, val);
            else
                update(2 * node + 2, mid + 1, end, idx, val);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
};

// ========================================================
ll fast_pow(ll base, ll exp, ll mod = MOD)
{
    ll res = 1;
    while (exp > 0)
    {
        if (exp % 2 == 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

vector<bool> is_prime;
void sieve(int n)
{
    is_prime.assign(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

void dfs(ll i, ll par, vvll &adj, vll &vis)
{
    vis[i] = 1;
    for (auto &ne : adj[i])
    {
        if (ne != par)
        {
            dfs(ne, i, adj, vis);
        }
    }
}

void solve()
{
    ll n;
    cin >> n;
    vll ar(n);
    fo(i, n)
    {
        cin >> ar[i];
    }
    ll sum = std::accumulate(all(ar), 0ll);
    if (sum % n != 0)
    {
        cout << -1 << '\n';
        return;
    }
    ll tar = sum / n;
    ll ans = 0;
    fo(i, n - 1)
    {
        ar[i + 1] += ar[i] - tar;
        ans += std::abs(ar[i] - tar);
        ar[i] = tar;
    }

    // ll ans = 0;

    cout << ans << endl;
}

int main()
{
    fast_cin();
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Submission Info

Judge Result