Codeforces #1019 : Div2 D. Local Construction

D問題までは簡単だった回。
https://codeforces.com/contest/2103/problem/D

問題

1～NのPermutation Bがあったとき、以下の手順を交互に繰り返してBの中身を減らしていく。

• Bのうち、local minimaではない要素を削除する
• Bのうち、local maximaではない要素を削除する

数列Pを、P[i]がB[i]が削除されるのが何回目かを示すように定める。
Pが当たられるので条件を満たすBを復元せよ。

解法

奇数回目では、そこで消される要素に値を大きい順に設定、偶数回目では、そこで消される要素に値を小さい順に設定…としていけばよい。

int T;
int N;
int A[202020];
int ret[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			if(A[i]==-1) A[i]=20;
			ret[i]=0;
		}
		int L=1,R=N;
		for(i=1;i<=19;i++) {
			FOR(j,N) {
				if(A[j]==i) {
					if(i%2) {
						ret[j]=R--;
					}
					else {
						ret[j]=L++;
					}
				}
				if(A[j]>i) break;
			}
			for(j=N-1;j>=0;j--) {
				if(A[j]==i) {
					if(i%2) {
						ret[j]=R--;
					}
					else {
						ret[j]=L++;
					}
				}
				if(A[j]>i) break;
			}
			FOR(j,N) if(A[j]==i&&ret[j]==0) {
				if(i%2) {
					ret[j]=R--;
				}
				else {
					ret[j]=L++;
				}
			}
		}
		FOR(j,N) if(A[j]==20) ret[j]=L;
		FOR(i,N) cout<<ret[i]<<" ";
		cout<<endl;
		
	}
}

まとめ

これはまぁ簡単だったね。