# D. Local Construction [문제 링크](https://codeforces.com/contest/2103/problem/D) ## Problem Statement An element $b_i$ ($1 \le i \le m$) in an array $b_1, b_2, \ldots, b_m$ is a **local minimum** if at least one of the following holds: - $2 \le i \le m-1$ and $b_i < b_{i-1}$ and $b_i < b_{i+1}$, or - $i = 1$ and $b_1 < b_2$, or - $i = m$ and $b_m < b_{m-1}$. Similarly, an element $b_i$ ($1 \le i \le m$) in an array $b_1, b_2, \ldots, b_m$ is a **local maximum** if at least one of the following holds: - $2 \le i \le m-1$ and $b_i > b_{i-1}$ and $b_i > b_{i+1}$, or - $i = 1$ and $b_1 > b_2$, or - $i = m$ and $b_m > $ $b_{m-1}$. Note that local minima and maxima are not defined for arrays with only one element. There is a hidden permutation$^{\ast}$ $p$ of length $n$. The following two operations are applied to permutation $p$ alternately, starting from operation 1, until there is only one element left in $p$: - **Operation 1** — remove all elements of $p$ which are **not** local minima. - **Operation 2** — remove all elements of $p$ which are **not** local maxima. More specifically, operation 1 is applied during every odd iteration, and operation 2 is applied during every even iteration, until there is only one element left in $p$. For each index $i$ ($1 \le i \le n$), let $a_i$ be the iteration number that element $p_i$ is removed, or $-1$ if it was never removed. It can be proven that there will be only one element left in $p$ after at most $\lceil \log_2 n \rceil$ iterations (in other words, $a_i \le \lceil \log_2 n \rceil$). You are given the array $a_1, a_2, \ldots, a_n$. Your task is to construct any permutation $p$ of $n$ elements that satisfies array $a$. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements in permutation $p$. The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le \lceil \log_2 n \rceil$ or $a_i = -1$) — the iteration number that element $p_i$ is removed. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is guaranteed that there exists at least one permutation $p$ that satisfies array $a$. ## Output For each test case, output $n$ integers representing the elements of the permutation satisfying array $a$. If there are multiple solutions, you may output any of them. ## Footnotes $^{\ast}$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). ## 풀이 #### level이 낮은 순부터 수를 배치하면 된다. 홀수번째 level에서는 -1의 왼쪽에서는 내림차순으로, -1의 오른쪽은 오름차순으로 배치하면 된다. 짝수번째 level에서는 -1의 왼쪽에서는 오름차순으로, -1의 오른쪽에서는 내림차순으로 배치하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int res[200'000], rootIdx; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vector<vector<int>> conn(n+1); for(int i=0;i<n;i++) { int level; cin >> level; if(level==-1) rootIdx=i; else conn[level].push_back(i); } int left=1, right=n; for(int level=1;level<=n;level++) { if(level%2==1) { int cnt=0; for(int j=0;j<conn[level].size();j++) { int idx = conn[level][j]; if(idx<rootIdx) { res[idx] = right-j; } else { res[idx] = right-conn[level].size()+1+cnt; cnt++; } } right -= conn[level].size(); } else { int cnt=0; for(int j=0;j<conn[level].size();j++) { int idx = conn[level][j]; if(idx<rootIdx) { res[idx] = left+j; } else { res[idx] = left+conn[level].size()-1-cnt; cnt++; } } left += conn[level].size(); } } res[rootIdx] = left; for(int i=0;i<n;i++) cout << res[i] << ' '; cout << '\n'; } } ```