【題解】Codeforces 1450D. Rating Compression

#include <bits/stdc++.h>
using namespace std;
 
int t, n, a[300005];
 
int main(){
    cin >> t;
    while (t--){
        cin >> n;
        int cnt[n+5] = {};
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            cnt[a[i]]++;
        }
        vector <int> ans;
        if (cnt[1]) ans.push_back(1);
        else ans.push_back(0);
        if (n == 1){
            cout << ans.back() << "\n";
            continue;
        }
        int l = 1, r = n;
        for (int k = n-1; k >= 2; k--){
            if (ans.back() == 0 || !cnt[n-k+1]){
                //cout << n-k+1 << " " << cnt[n-k+1] << "\n";
                ans.push_back(0);
                continue;
            }
            if (cnt[n-k] != 1 || (a[l] != n-k && a[r] != n-k)){
                ans.push_back(0);
                //cout << k << " " << n-k << " " << cnt[n-k] << " " << l << " " << a[l] << " " << r << " " << a[r] << "\n";
            }
            else{
                if (a[l] == n-k) l++;
                else r--;
                ans.push_back(1);
            }
        }
        if (*max_element(cnt+1, cnt+n+1) == 1 && *min_element(cnt+1, cnt+n+1) == 1){
            ans.push_back(1);
        }
        else ans.push_back(0);
        reverse(ans.begin(), ans.end());
        for (int i:ans){
            cout << i;
        }
        cout << "\n";
    }
}