1853D - Imbalanced Arrays - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;
#define dbg(x...) do { cout << #x << "  -> "; err(x); } while (0);
void err() {cout << endl; }
template<class T, class... Ts> void err(const T& arg, const Ts&... args) {cout << arg << " "; err(args...); }

#define int long long 
#define pb push_back
#define pii pair<int,int>
#define endl '\n'
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int M = 50;
void solve() {
    int n; cin >> n;
    vector<int> a(n), p(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j){
        return a[i] < a[j];
    });
    int l = 0, r = n - 1, os = 0;
    vector<int> ans(n, 0);
    for (int i = n; i >= 1; i--) {
        // dbg(i, os, l, r, a[p[l]] - os, a[p[r]] - os);
        if (a[p[l]] - os != 0 && a[p[r]] - os != i) {
            cout << "NO" << endl;
            return;
        } 
        if (a[p[l]] - os == 0) {
            ans[p[l]] = -i;
            l++;
        } else {
            ans[p[r]] = i;
            os++;
            r--;
        }
    }
    cout << "YES" << endl;
    for (auto &x : ans)
        cout << x << " ";
    cout << endl;
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int testcase; cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}