Codeforces Round #529 (Div. 3)D. Circular Dance

問題概要

n 人が円になって並んでおり, 人 i について 1 つ先の人, 及び 2 つ先の人は a_{i, 1}, a_{i, 2} である. なお, a_{i, 1}, a_{i, 2} は順番が逆のこともある( a_{i, 1} が二つ先の人を表していることもある). もとの順番 p を復元せよ.

問題へのリンク

制約

  • 3 \le n \le 2\times 10^5
  • 1 \le a_{i, 1}, a_{i, 2} \le n
  • 解は必ず一つ以上存在する. 

解説

最初を人 1 としましょう. 次の人の候補は a_{1, 1}, a_{1, 2} のいずれかですが, このうち a_{1, 1} が次の人の場合, a_{a_{1, 1}, 1} か a_{a_{1, 1}, 2} のいずれかが a_{1, 2} と等しくなります(自分にとって 2 つ先の人は自分の 1 つ先の人にとっては 1 つ先の人ということ.). ですから, a_{1, 1}, a_{1, 2} のどちらが自分の次かを毎回定数回で判定できるので, 愚直にシミュレーションすればいいです.

エッジケースは n=3 です. この場合, 1, 2, 3 と 1, 3, 2 を与えられた情報から区別することが不可能なので, 毎回 1, 2, 3 を出力すればいいです.

 実装

Submission #145850079 - Codeforces