俺のchokudai Searchが遅すぎる

chokudai searchをするときに余裕を持ってTime Limitを設定してもTLEしてしまう話と解決法

問題

先日AHC002がありました．そこでchokudai seachを実装したのですが，TLを1600msにしてもTLEになってしまうことが多々ありました．

f:id:qlethon:20210426101339p:plain

次のような実験をしたところ，関数のreturn直前ではTLくらいの時間しか経っていないにも関わらず，return直後ではTL + 数100ms経っていることが分かりました．

void chokudai_search(){
    /* メインの処理 */
    
    時間の計測  // 1630ms
    return;
}

int main{
    /* 前処理 */
    
    chokudai_search();
    時間の計測  // 2030ms
}

時間はテキトーですが，だいたいこんな感じです．

このことからchokudai searchで使った大量のキューの後処理が関数から返る時に走っていて，それが重いのだと予測しました．

解決法

関数から返る前に出力を済ませexit()を使う．

せや！関数から返る時の処理が重いんだったら返らなければええんや！と思い，次のようにしました．

void chokudai_search(){
    /* メインの処理 */
    
    答えの出力
    exit(0);  // ここでプログラムを終了する
}

int main{
    /* 前処理 */
    
    chokudai_search();
}

すると，だいたいTLくらいで終わるようになりました．

f:id:qlethon:20210426102600p:plain
TLは1700ms

さらに，ドキュメントを見るとexit()より早いquick_exit()があることが分かります．しかし，実験をするとなぜかexit()より遅いです． TLは1950msです．

さいごに

exit()が早い理由，quick_exit()がexit()より遅い理由，abort()が遅い理由すべて分かりません！！！！有識者HELP！！！！！！！！！！！！！

qLethonの提出 - https://atcoder.jp/contests/ahc002/submissions?f.User=qLethon