62D2qV - Online C++ Compiler & Debugging Tool

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int main() {
	//cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<int> a(n);
		vector<pair<int, int>> alive; // {a[i], i}
		for (int &x : a) {
			cin >> x;
			if (x == -1) x = n + 1;
		}

		for (int i = 0; i < n; i++) {
			alive.push_back(make_pair(a[i], i));
		}

		vector<int> l(n), r(n);
		for (int i = 0; i < n; i++) {
			l[i] = i - 1;
			r[i] = i + 1;
		}

		vector<vector<int>> adj(n);
		sort(alive.rbegin(), alive.rend());

		vector<int> indegree(n, 0), ans(n);

		int step = 1;
		while (alive.size() > 1) {

			// (u, v) -> p[u] > p[v]
			for (auto p : alive) {
				if (p.first == step) continue;
				int u = p.second;
				if (l[u] >= 0) {
					if (step % 2 == 1) { // u is local min
						adj[l[u]].push_back(u);
						indegree[u]++;
					} else {
						adj[u].push_back(l[u]);
						indegree[l[u]]++;
					}
				}
				if (r[u] < n) {
					if (step % 2 == 1) {
						adj[r[u]].push_back(u);
						indegree[u]++;
					} else {
						adj[u].push_back(r[u]);
						indegree[r[u]]++;
					}
				}
			}
			while (alive.size() > 0 && alive.back().first == step) {
				int idx = alive.back().second;
				if (l[idx] >= 0) r[l[idx]] = r[idx];
				if (r[idx] < n) l[r[idx]] = l[idx];
				alive.pop_back();
			}
			step++;
		}

		// for (int i = 0; i < n; i++) {
		// 	for (int j : adj[i]) {
		// 		cout << "(" << i << ", " << j << ")" << '\n';
		// 	}
		// }

		queue<int> q;
		for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);

		int val = n;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			ans[u] = val--;
			for (int v : adj[u]) {
				indegree[v]--;
				if (indegree[v] == 0) q.push(v);
			}
		}

		for (int x : ans) cout << x << ' ';
		cout << '\n';
	}
}