ACM-ICPC 2016 Asia Tsukuba Regional, A 解法

A: Rearranging a Sequence

問題

始めに数列1 … n がある。「数e_iを先頭に移動させる」と言う操作をm回行う（1 <= i <= m）。最後の数列を出力せよ。

解法

操作を後ろから見ていき、初めて見た数を順に拾い上げる。それらを先に出力し、残りは昇順に出力する。

コード

#include<stdio.h>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

int N, M;
int E[200111];
bool use[200111];

int main() {

    scanf("%d%d", &N, &M);
    REP (i, M) scanf("%d", E+i);

    for (int i=M; i--;) {
	if (!use[E[i]]) {
	    use[E[i]] = true;
	    printf("%d\n", E[i]);
	}
    }

    for (int i=1; i<=N; i++) if (!use[i]) {
	printf("%d\n", i);
    }

    return 0;
}

感想

優しさにあふれる問題。