B. Dreamoon Likes Permutations (Codeforces Round #631 Div. 2)

問題

https://codeforces.com/contest/1330/problem/B

問題概要

長さl1の順列p1と長さl2の順列p2がある。

長さn = l1 + l2の数列aが与えられるので、これをp1とp2に分割可能であるかを答えよ。分割可能であれば、分割位置も全て答えよ。

考察

以下簡単のためl1 < l2で考えます。数列aの項の最大値は、p2の項の最大値であり、l2そのものです。よって、まずaの項の最大値がわかればl2が確定します。l2がわかればn = l1 + l2なので、l1はn - l2であることもわかります。

よって、確認すべきは左がl1で右がl2になるか、左がl2で右がl1になるように分割する2種類だけとなります。

ただしl1 = l2のときは分割位置がたかだか一つであることに注意です。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int l2 = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            l2 = max(l2, a[i]);
        }
        int l1 = n - l2;

        auto check = [&](int start, int end) {
            int len = end - start;
            vector<bool> used(len + 1, false);
            for (int i = start; i < end; i++) {
                if (a[i] > len || used[a[i]]) {
                    return false;
                }
                used[a[i]] = true;
            }
            return true;
        };

        vector<pair<int, int>> ans;
        if (check(0, l1) && check(l1, n)) {
            ans.emplace_back(l1, n - l1);
        }
        if (l1 != l2 && check(0, l2) && check(l2, n)) {
            ans.emplace_back(l2, n - l2);
        }

        cout << ans.size() << endl;
        for (auto p : ans) {
            cout << p.first << " " << p.second << endl;
        }
    }
}