結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー onexisanonexisan
提出日時 2015-05-20 11:29:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 380 ms / 5,000 ms
コード長 1,282 bytes
コンパイル時間 1,389 ms
コンパイル使用メモリ 158,036 KB
実行使用メモリ 7,564 KB
最終ジャッジ日時 2023-09-20 10:26:44
合計ジャッジ時間 8,935 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 380 ms
7,316 KB
testcase_01 AC 377 ms
7,220 KB
testcase_02 AC 378 ms
7,268 KB
testcase_03 AC 362 ms
7,348 KB
testcase_04 AC 368 ms
7,564 KB
testcase_05 AC 365 ms
7,376 KB
testcase_06 AC 375 ms
6,568 KB
testcase_07 AC 379 ms
6,980 KB
testcase_08 AC 360 ms
6,544 KB
testcase_09 AC 364 ms
6,948 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)

const int N = 100010;

int n, L[N], q, k[N];

void input()
{
    cin >> n;
    rep(i, n) cin >> L[i];
    cin >> q;
    rep(i, q) cin >> k[i];
}

double ans[N];

void solve()
{
    vector<pair<int, int>> queries;
    rep(i, q) queries.emplace_back(k[i], i);
    sort(begin(queries), end(queries));
    struct entry {
        int id, num; double len;
        entry(int id, int num, double len) : id(id), num(num), len(len) {}
        bool operator <(const entry& t) const { return len < t.len; }
    };
    priority_queue<entry> que;
    rep(i, n) que.emplace(i, 1, L[i]);
    int i = 0, cnt = 0;
    while (i < q) {
        auto e = que.top();
        que.pop();
        ++cnt;
        while (i < q and queries[i].first <= cnt) {
            ans[queries[i++].second] = e.len;
        }
        que.emplace(e.id, e.num + 1, double(L[e.id]) / (e.num + 1));
    }
    rep(i, q) cout << ans[i] << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    input();
    solve();
}
0