結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー tottoripapertottoripaper
提出日時 2014-11-17 19:43:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 522 ms / 5,000 ms
コード長 1,164 bytes
コンパイル時間 987 ms
コンパイル使用メモリ 52,620 KB
実行使用メモリ 36,872 KB
最終ジャッジ日時 2023-08-30 20:30:07
合計ジャッジ時間 14,192 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 434 ms
36,872 KB
testcase_01 AC 434 ms
36,688 KB
testcase_02 AC 433 ms
36,680 KB
testcase_03 AC 505 ms
36,632 KB
testcase_04 AC 522 ms
36,816 KB
testcase_05 AC 504 ms
36,768 KB
testcase_06 AC 427 ms
35,592 KB
testcase_07 AC 424 ms
36,120 KB
testcase_08 AC 466 ms
35,344 KB
testcase_09 AC 495 ms
35,772 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>

struct Heap{
    double value;
    int index;
    Heap *left, *right;
};

Heap* meld(Heap* a, Heap* b){
    if(a == nullptr){return b;}
    if(b == nullptr){return a;}

    if(a->value < b->value){std::swap(a, b);}

    a->right = meld(a->right, b);
    std::swap(a->left, a->right);
    
    return a;
}

double ls[100000], maxLength[500001];
int ts[100000];

int main(){
    int N;
    scanf("%d", &N);

    std::fill(ts, ts+N, 1);

    Heap *h = nullptr;

    for(int i=0;i<N;i++){
        scanf("%lf", ls+i);
        
        Heap *e = new Heap{ls[i], i, nullptr, nullptr};
        h = meld(h, e);
    }

    for(int k=1;k<=500000;k++){
        Heap *max_e = h;
        maxLength[k] = max_e->value;
        
        int index = max_e->index;
        ts[index] += 1;
        Heap *new_e = new Heap{ls[index]/ts[index], index, nullptr, nullptr};
        h = meld(new_e, meld(max_e->left, max_e->right));
    }

    int Q;
    scanf("%d", &Q);
    
    for(int i=0;i<Q;i++){
        int k;
        scanf("%d", &k);

        printf("%.30f\n", maxLength[k]);
    }
}
0