結果

問題 No.3221 Count Turns
ユーザー srjywrdnprkt
提出日時 2025-08-10 23:59:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 1,833 bytes
コンパイル時間 2,807 ms
コンパイル使用メモリ 286,304 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-10 23:59:43
合計ジャッジ時間 5,141 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

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

    /*
       例の場合、
       A_1は4回でCに1足され、A_2は3回でCに1足される。
       12の周期で一致するがA_1*4<A_2*3なのでA_2の方が先
       二分探索で何回操作したらCに足される回数がT以上になるか求める。
       f(X) = X回操作した時、Cに足される回数がT以上か？
       を見たす最小のrを求める。r-1回目まではT回を超えないので楽に計算できる。
       r回目は愚直にやる。
    */

    ll N, H, T;
    cin >> N >> H >> T;
    vector<ll> A(N), period(N), C(N);
    for (int i=0; i<N; i++){
        cin >> A[i];
        period[i] = (H+A[i]-1)/A[i];
    }
    //X回操作したときにCに足される回数
    auto f=[&](ll X)->ll{
        ll res = 0;
        for (int i=0; i<N; i++){
            res += X/period[i];
            if (res > T) return T+1;
        }
        return res;
    };

    ll l=0, r=1e18, c;
    while(r-l>1){
        c = (l+r)/2;
        if (f(c)>=T) r=c;
        else l=c;
    }
    for (int i=0; i<N; i++){
        C[i] += (r-1)/period[i];
        T -= (r-1)/period[i];
    }
    //周期がrの約数であるようなA_iについてA_i*period_iが大きい順に、同じならiが小さい順に足す。
    vector<pair<ll, ll>> v;
    for (int i=0; i<N; i++){
        if (r % period[i] == 0){
            v.push_back({-A[i]*period[i], i});
        }
    }
    sort(v.begin(), v.end());
    for (int i=0; i<T; i++){
        auto [x, y] = v[i];
        C[y]++;
    }
    for (int i=0; i<N; i++) cout << C[i] << " ";
    cout << endl;

    return 0;
}
0