ABC 401-500/ABC406D - Garbage Removal - 競技プログラミング用 知識集積所

---

問題

ABC406D

必要知識

B以下レベルの内容は省略

• set（未作成）

考え方

二次元グリッドにゴミを配置しようとすると、マスの数が多すぎて、グリッドの用意だけでTLEする。
そこで、各行各列ごとに「何番目のマスにゴミがあるか」を管理することにする。

ゴミが何個あるかは、データサイズを見ればよい。
ゴミを取り除くには、その行または列が持っているデータからゴミ位置を復元してやればよい。

計算量は、この形式なら各ゴミについて「1回置いて、1回取り除く」の負担があるだけなので何も問題にならない。

解答例

解答例

注意点

unordered_multisetではTLEする

ソートしない分速いかと思いきや全然そんなことはなく、TLEする。
→失敗例（上の解答例とunorderedかどうかが違うだけ）
おそらく、ハッシュ衝突のせい？

別解