CF-1019-D. Local Construction · znzryb

## 思路讲解

```
// 要求你构造一个数组，符合A中的要求，如果A[1]=1，那么就说明这个
// 构造数组中的这个元素需要于第一次操作时去除。A[2]=-1，说明第二个元素被剩下了。
// 奇数次操作只留下局部最小值，偶数次操作只留下局部最大值（严格）。

```

## AC代码

[https://codeforces.com/contest/2103/submission/318747498](https://codeforces.com/contest/2103/submission/318747498)



::: 源代码

```cpp
// Problem: D. Local Construction
// Contest: Codeforces - Codeforces Round 1019 (Div. 2)
// URL: https://codeforces.com/contest/2103/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
vector<ll> g[MAXN];
ll pos_=0;

inline void solve(){
	cin>>N;
	pos_=0;
	FOR(i,1,N) g[i].clear();
	FOR(i,1,N){
		cin>>A[i];
		if(A[i]==-1) pos_=i;
		g[A[i]].pb(i);
	}
	ll Low=1,Up=N;
	FOR(i,1,ceil(log2(N)) ){
		ll bp=INF;
		FOR(j,0,SZ(g[i])-1){
			ll node=g[i][j];
			if(node>pos_){
				bp=j;
				break;
			}
			if(i%2==1){
				A[node]=Up--;
			}else{
				A[node]=Low++;
			}
		}
		ROF(j,SZ(g[i])-1,bp){
			ll node=g[i][j];
			if(i%2==1){
				A[node]=Up--;
			}else{
				A[node]=Low++;
			}
		}
	}
	A[pos_]=Low++;
	FOR(i,1,N){
		cout<<A[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2103/submission/318747498
*/
```


:::


## 心路历程（WA，TLE，MLE……）