結果

問題 No.68 よくある棒を切る問題 (2)
ユーザー tottoripapertottoripaper
提出日時 2014-11-17 19:43:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 428 ms / 5,000 ms
コード長 1,164 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 57,016 KB
実行使用メモリ 36,864 KB
最終ジャッジ日時 2024-06-10 19:59:07
合計ジャッジ時間 11,972 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 374 ms
36,864 KB
testcase_01 AC 378 ms
36,788 KB
testcase_02 AC 383 ms
36,864 KB
testcase_03 AC 427 ms
36,864 KB
testcase_04 AC 428 ms
36,864 KB
testcase_05 AC 426 ms
36,828 KB
testcase_06 AC 369 ms
35,584 KB
testcase_07 AC 371 ms
36,096 KB
testcase_08 AC 398 ms
35,172 KB
testcase_09 AC 410 ms
35,712 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:27:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   27 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%lf", ls+i);
      |         ~~~~~^~~~~~~~~~~~~
main.cpp:51:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
main.cpp:55:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~

ソースコード

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