小X与队列

小X与队列

时间限制: 1 Sec  内存限制: 128 MB

题目描述

小X正和同学们做列队的练习。
有n名同学排成一路纵队，编号为i的同学排在从前往后数第i个位置上，即：初始时的队列为1, 2, 3, ..., n。
接下来小X会发出若干条指令，每条指令形如“请编号为x的同学排到最前面来”。（例如：若当前时刻的队列为5, 4, 3, 2, 1，发出一条x=2的指令后，队列变成了2, 5, 4, 3, 1。）
小X发出了很多很多指令，同学们晕头转向不知道该怎么排列。于是就请你算一算，执行完这些指令后，队列应该变成什么样？

输入

第一行两个用空格隔开的正整数n和m，分别表示人数和指令数。
第二行m个用空格隔开的正整数x[i]，按顺序表示每次指令的x值。

输出

输出仅有一行包含n个正整数，相邻两个数之间用一个空格隔开，表示执行完所有指令后的队列。

样例输入

复制样例数据

4 3
2 3 2

样例输出

2 3 1 4

提示

样例解释
第一条指令前：1 2 3 4
第一条指令后(x=2)：2 1 3 4
第二条指令后(x=3)：3 2 1 4
第三条指令后(x=2)：2 3 1 4

数据范围
对于30%的数据，1<=n,m<=1000
对于另外30%的数据，n=m，且1～n每个数在x[i]中恰好出现一次。
对于100%的数据，1<=n,m<=100000

从后往前遍历一遍，因为后面的肯定放在最前面。如果从后往前遇到相同的值，跳过。

最后从小到大遍历一遍1~n，如果已经访问过这个值，跳过，否则输出

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
int a[100005], vis[100005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++){
		scanf("%d", &a[i]);
	}
	for (int i = m; i >= 1; i--){
		if(vis[a[i]]) continue;
		vis[a[i]] = 1;
		printf("%d ", a[i]);
	}
	for (int i = 1; i <= n; i++){
		if(!vis[i]) printf("%d ", i);
	}
	printf("\n");

	return 0;
}
/**/