Submission #22472334

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (auto i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()

using namespace std;

using ll = long long int;

const int MOD_NUM = 1e9 + 7;

int main() {
    // Input
    int K, N, M;
    cin >> K >> N >> M;
    vector<int> A(K);
    rep(i, K) cin >> A[i];

    // Process
    const double rate = (double)M / N;

    // before round
    vector<double> b(K);
    rep(i, K) b[i] = A[i] * rate;

    // after the decimal point
    vector<pair<double, int>> pair_for_sort(K);
    rep(i, K) pair_for_sort[i] = make_pair(fmod(b[i], 1.0), i);
    sort(ALL(pair_for_sort));
    vector<double> fractional_parts(K);
    vector<int> indexes(K);
    rep(i, K) {
        fractional_parts[i] = pair_for_sort[i].first;
        indexes[i] = pair_for_sort[i].second;
    }

    // rounded
    vector<ll> B(K);
    rep(i, K) B[i] = (ll)round(b[i]);

    // sum B
    const ll sum_b = accumulate(ALL(B), 0);

    // adjust
    const int half =
        lower_bound(ALL(fractional_parts), 0.5) - fractional_parts.begin();

    if (sum_b > M) {
        rep(i, sum_b - M) {
            int index = (half + i) % K;
            B[indexes[index]]--;
        }
    }
    if (sum_b < M) {
        rep(i, M - sum_b) {
            int index = (half - 1 - i + K) % K;
            B[indexes[index]]++;
        }
    }

    // Output
    rep(i, K) {
        if (i > 0) cout << ' ';
        cout << B[i];
    }
    cout << endl;

    return 0;
}

Submission Info

Judge Result