結果

問題 No.3051 Make All Divisible
ユーザー rin204
提出日時 2025-02-03 22:53:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,192 bytes
コンパイル時間 10,401 ms
コンパイル使用メモリ 357,196 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-08 15:05:01
合計ジャッジ時間 13,016 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include "testlib.h"

void solve() {
    int n = inf.readInt(1, 2000);
    inf.readSpace();
    int K = inf.readInt(1, n);
    inf.readEoln();
    std::vector<long long> A = inf.readLongs(n, 0LL, 1'000'000'000'000'000);
    std::sort(A.begin(), A.end());
    inf.readEoln();

    std::vector<long long> C(n);
    {
        long long tot = 0;
        for (int i = 0; i < n; i++) {
            C[i] = A[i] % K;
            tot += C[i];
        }
        if (tot % K != 0) {
            std::cout << -1 << std::endl;
            return;
        }
    }

    auto ok = [&](long long x) -> bool {
        long long tot = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] < x) {
                tot += A[i];
            } else {
                if (x < C[i]) {
                    return false;
                }
                tot += (x - C[i]) / K * K + C[i];
            }
        }

        return x <= tot / K;
    };

    long long rr        = A[n - K] - 1 + K;
    const long long inf = 1LL << 62;
    long long max_c     = inf;
    for (int d = 0; d < K; d++) {
        long long ma = (rr - d) / K * K + d;
        if (!ok(ma)) continue;
        long long l = -1;
        long long r = ma / K;
        while (r - l > 1) {
            long long mid = (l + r) >> 1;
            if (ok(mid * K + d)) {
                r = mid;
            } else {
                l = mid;
            }
        }

        if (r * K + d < max_c) max_c = r * K + d;
    }
    if (max_c == inf) {
        std::cout << -1 << std::endl;
        return;
    }

    long long tot     = 0;
    long long max_cnt = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] <= max_c) {
            tot += A[i];
            if (A[i] == max_c) max_cnt++;
        } else {
            tot += (max_c - C[i]) / K * K + C[i];
        }
    }
    tot /= K;
    if (max_c < K) max_cnt = 0;
    long long ans = std::max(max_c, tot - max_cnt);
    std::cout << ans << std::endl;
}

int main(int argc, char *argv[]) {
    std::cin.tie(0)->sync_with_stdio(0);
    registerValidation(argc, argv);
    int T = inf.readInt(1, 2000);
    inf.readEoln();
    while (T--) solve();
    inf.readEof();
}
0