結果

問題 No.68 よくある棒を切る問題 (2)
コンテスト
ユーザー tottoripaper
提出日時 2014-11-17 19:43:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 443 ms / 5,000 ms
コード長 1,164 bytes
記録
コンパイル時間 748 ms
コンパイル使用メモリ 61,460 KB
実行使用メモリ 37,016 KB
最終ジャッジ日時 2025-01-02 16:51:06
合計ジャッジ時間 12,670 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

#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