基本方針

基本的には各位置のボールに書かれている整数が何かに注目して操作をシミュレーションし、最終的な並びを求めることになります。
左から \(i\) 番目のボールに書かれている整数を表す変数を \(val[i]\) とします。

初め、左から \(i(1 \leq i \leq N)\) 番目のボールには整数 \(i\) が書かれています。

という記述に従い、\(val\) は次のように初期化を行います。

vector<int> val(N+1);
for(int i=1;i<=N;i++)val[i] = i;

そして、\(Q\) 回の操作は以下のようにしてシミュレーション出来ます。

for(int i=0;i<Q;i++){
	for(int j=1;j<=N;j++){
		if(val[j]==x[i]){
			if(j!=N)swap(val[j],val[j+1]);
			else swap(val[j],val[j-1]);
			break;
		}
	}
}

しかし、このシミュレーションの時間計算量は \(\mathrm{O}(NQ)\) であり、本問の制約の下で実行時間制限に間に合わせるには改善が必要です。

\(\mathrm{O}(Q)\) への改善

上のコードでは \(Q\) 回のループ内で \(val[j]=x[i]\) となる \(j\) を \(\mathrm{O}(N)\) かけて求めていますが、整数 \(j\) が書かれているボールが左から何番目かを表す変数 \(pos[j]\) を管理することでこの部分を \(\mathrm{O}(1)\) に出来、十分高速に本問を解くことが出来ます。

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N;
	cin>>N;
	
	vector<int> val(N+1),pos(N+1);
	for(int i=1;i<=N;i++)val[i] = i,pos[i] = i;
	
	int Q;
	cin>>Q;
	
	vector<int> x(Q);
	for(int i=0;i<Q;i++)cin>>x[i];
	
	for(int i=0;i<Q;i++){
		int p0 = pos[x[i]];
		int p1 = p0;
		if(p0!=N)p1++;
		else p1--;
		int v0 = val[p0];
		int v1 = val[p1];
		swap(val[p0],val[p1]);
		swap(pos[v0],pos[v1]);
	}
	
	for(int i=1;i<=N;i++){
		if(i!=1)cout<<' ';
		cout<<val[i];
	}
	cout<<endl;
	
    return 0;
}