B. Dreamoon Likes Permutations

Link

Solution

关键在于如果数组可被恰好分为两个排列，那么一定会被分为长度为k的k排列和长度为n-k的n-k排列，其中k或n-k为数组最大值。于是找到数组最大值maxv后判断[0, maxv)，[maxv, n)和[0, n - maxv)，[n - maxv, n)是否都为合法排列即可。

Code

int a[maxn], vis[maxn], n;

bool judge(int l, int r, int mv) {
    for (int i = 0; i <= n; i++)vis[i] = 0;
    for (int i = l; i < r; i++)vis[a[i]] = 1;
    for (int i = 1; i <= mv; i++)if (!vis[i])return false;
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int maxv = -1, flag1 = 0, flag2 = 0;
        cin >> n;
        for (int i = 0; i < n; i++) { cin >> a[i]; maxv = max(a[i], maxv); }
        if (judge(0, maxv, maxv) && judge(maxv, n, n - maxv))flag1 = maxv;
        maxv = n - maxv;
        if (judge(0, maxv, maxv) && judge(maxv, n, n - maxv))flag2 = maxv;
        if (flag1&&flag2&&flag1 != flag2) {
            cout << 2 << endl;
            cout << flag1 << " " << n - flag1 << endl;
            cout << flag2 << " " << n - flag2 << endl;
        }
        else if (flag1) {
            cout << 1 << endl;
            cout << flag1 << " " << n - flag1 << endl;
        }
        else if (flag2) {
            cout << 1 << endl;
            cout << flag2 << " " << n - flag2 << endl;
        }
        else cout << 0 << endl;
    }
    return 0;
}