Решение задачи "Dreamoon любит перестановки" с Codeforces

Без пояснения   Просмотров: 18


Последовательность из m целых чисел называется перестановкой, если она содержит все целые числа от 1 до m ровно один раз. Число m называется длиной перестановки.

У Dreamoon есть две перестановки p1 и p2 имеющих ненулевые длины l1 и l2.

Затем, Dreamoon конкатенирует эти две перестановки в последовательность a длины l1+l2. Первые l1 элементов a это перестановка p1 а следующие l2 элементов a это перестановка p2.

Вам дана последовательность a, вам нужно найти восстановить перестановки p1 и p2. Если есть несколько возможных способов, вам нужно найти все. (Обратите внимание, что также возможно, что способов не будет.)

Код

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

const int N = 2e5 + 1;

int t,n;
vector<pair<int,int> > ans;
int a[N],f[N],b[N];
set<int> s;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1;i <= n;i++) cin >> a[i];
        int mx = 0;
        s.clear();
        for(int i = 1;i <= n;i++) s.insert(a[i]),mx = max(mx,a[i]),f[i] = (mx==i and s.size()==i);
        mx = 0; s.clear();
        for(int i = n;i >= 1;i--) s.insert(a[i]),mx = max(mx,a[i]),b[i] = (mx==n-i+1 and s.size()==n-i+1);
        ans.clear();
        for(int i = 1;i < n;i++) if(f[i] and b[i+1]) ans.push_back({i,n-i});
        cout << ans.size() << '\n';
        for(auto x : ans) cout << x.first << ' ' << x.second << '\n';
    }
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться