結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー GOTKAKO
提出日時 2025-06-29 23:58:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 280 ms / 5,000 ms
コード長 859 bytes
コンパイル時間 2,384 ms
コンパイル使用メモリ 209,068 KB
実行使用メモリ 10,564 KB
最終ジャッジ日時 2025-06-29 23:58:38
合計ジャッジ時間 12,999 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;
    vector<double> L(N);
    for(auto &l : L) cin >> l;
    sort(L.rbegin(),L.rend());
    vector<double> answer(500001);
    priority_queue<tuple<double,int>> Q;
    int Log = 0,pos = 1;
    double now = L.at(0);
    vector<int> use(N); 
    Q.push({L.at(0)/2,0});
    answer.at(++Log) = now,use.at(0) = 1; 
    while(Log < 500000){
        auto [next,u] = Q.top();
        if(pos < N && next < L.at(pos)) next = L.at(pos),u = pos++;
        else Q.pop();
        now = next; use.at(u)++;
        Q.push({L.at(u)/(1+use.at(u)),u});
        answer.at(++Log) = now;
    }

    cout << fixed << setprecision(20);
    int q; cin >> q;
    while(q--){
        int K; cin >> K;
        cout << answer.at(K) << "\n";
    }
}
0