AtCoder ARC #110 （鹿島建設プログラミングコンテスト2020） : C - Exoswap

最近またAtCoder系調子よくないな。
https://atcoder.jp/contests/arc110/tasks/arc110_c

問題

1～NのPermutationである数列Pが与えられる。
P[i]とP[i+1]を入れ替える、という動作を、各i=1～(N-1)に対し1回ずつ任意の順で実行できるとする。
Pをソースできるか判定し、その手順を答えよ。

解法

貪欲に1から順に正しい位置に持っていこう。
同じ場所で2回以上入れ替えが生じたら即失敗扱いすればO(N)で済む。

int N;
int P[202020],R[202020];
vector<int> ret;
int did[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		R[P[i]]=i;
	}
	
	FOR(i,N) {
		x=R[i];
		while(x>i) {
			if(did[x-1]==1) return _P("-1\n");
			did[x-1]=1;
			ret.push_back(x);
			swap(P[x-1],P[x]);
			R[P[x]]=x;
			R[P[x-1]]=x-1;
			x--;
		}
	}
	FOR(i,N-1) if(did[i]==0) return _P("-1\n");
	FORR(r,ret) cout<<r<<endl;
}

まとめ

Dまでは順調だったんだけどなぁ。