AtCoder Regular Contest 042 A - 掲示板

問題
http://arc042.contest.atcoder.jp/tasks/arc042_a

N個の掲示板のスレッド1〜Nがある。はじめ、番号順に上から並んでいる。
あるスレッドに書き込みがおこると、そのスレッドが一番上位になる。
時系列順にM回の書き込まれたスレッド番号が入力される。
最終的なスレッドの順序を求めよ。
N, M <= 10^5

解法
同じスレッドの書き込みのついて、より後ろの方のみ考慮すればよい。
つまり、書き込みのクエリを後ろから読んで、各スレッドに対してはじめに書かれたもののみ採用すれば良い。
一度も書き込まれていないスレッドは、一度以上書き込まれたスレッドの後に、番号順に並ぶことになる。

int main() {
 
  int N, M; cin >> N >> M;
  int a[M]; rep(i, M) cin >> a[i], a[i]--;
  bool used[N]; zero(used);
  for(int i=M-1; i>=0; i--) {
    if(!used[a[i]]) {
      cout << a[i] + 1 << endl;
      used[a[i]] = 1;
    }
  }
 
  rep(i, N) if(!used[i])
    cout << i + 1 << endl;
 
  return 0;
}