Velocity

方向を定めて

AOJで、出力結果は合っているように見えるWAでハマった

TL;DR

  • ios::sync_with_stdio(false) を削除するとACだった
  • ios::sync_with_stdio(false) を削除せず、endlを"\n"に置き換えてもACだった
  • 同期を切っていることが問題ではなく、バッファのフラッシュ回数が原因？

発端

Stable Sortを解いていた、コードを書き自信満々でSubmit

"WA"

悲しい2文字が出力された、4つ目のテストケースで落ちている、どこがおかしいんだ。
まぁシュっと修正して早く次の問題やろう。


コード・出力とにらめっこしつつ、ハマり始めて30分...

やっぱり分からない。ロジックも問題なさそうに見える。
仕方ないので、他の回答者の方のコードを拝借し、ローカルで出力を比較する。

# 自分の出力
H3 D3 S3 S4 C4 H4 S5 H5 D5
Stable
H3 D3 S3 H4 C4 S4 D5 S5 H5
Not stable
# 正しい出力
H3 D3 S3 S4 C4 H4 S5 H5 D5
Stable
H3 D3 S3 H4 C4 S4 D5 S5 H5
Not stable

...同じじゃねえかーーーーーーーーーーーーーー！！！
なぜだ、なぜなんだ。出力が正しければ良いのが竸プロという世界ではないのか（偏見）

いよいよ分からなくなってきた、竸プロは難しい。

メンタルを試されているのか...?

段々と「出力は間違っていない、処理中に問題が発生しているに違いない」という謎思考になってくる。 もはや自分の偏見さえも覆している。

原因は入力方法

ここで参考にしていたコードの人の入力方法を確認すると、自分のコードと違いがあることに気づく。 自分と同じくcinでの入力方法を用いているが、cinとcout、iostreamとstdioの同期を切っていないことに気づく。

入力なんて関係ないだろう、とは思いつつなんとなく同期を切るコードを削除してみる。

// cin.tie(0);
// ios::sync_with_stdio(false);

Submit


"AC"

...同期〜〜〜〜〜〜〜〜〜〜〜！！！ さらに ios::sync_with_stdio(false); だけ削除してSubmitしてもACになることが判明。

念願のACとはいえ、今後もハマる可能性が大いにあり得るので、入力についてちょっと調べてみる。

ここで、International Olympiad In Informatics 2009, Technical Info Sheet（日本訳） を見つける。 https://www.ioi-jp.org/ioi/2009/problems/day2/Technical_jp.pdf

どうやら ios::sync_with_stdio(false) で同期を切る場合は、endl ではなく "\n" での改行が推奨されているらしい。 endlでの改行と"\n"での改行を違いを、後者の方がちょっと早いという認識でしかなかったが、とりあえずこれも試してみることにした。

ios::sync_with_stdio(false)を再度記述し、endlを全て"\n"に置き換えてみて、Submit。

"AC"

なんとACだ。正直びびった。 不思議に思いつつ、endlと"\n"の違いについて調べてみる。

  • endl

    • 改行を出力し、バッファをフラッシュする

  • "\n"

    • 改行を出力する

なるほど、バッファをフラッシュするか否かの差異があるらしい。

この記事などが参考になった。 C++ の endl とか flush の存在意義 - ハトネコエ Web がくしゅうちょう

まとめ

TL;DRに書いてあることが自分の中での結論。 結局、今回の問題がコードの問題かAOJ特有の問題かは分からず、根本原因を解明した訳ではないが同じようにハマっている誰かの助けになれば幸いだ。

今までは視認性からendlを用いていたが、これからは"\n"を使用することにしよう。