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; }