Дана перестановка 𝑝∗ чисел от 1 до 𝑛. Для произ...

Question

Дана перестановка 𝑝∗ чисел от 1 до 𝑛.

Для произвольной перестановки 𝑞 длины 𝑛 будем говорить, что индекс 𝑗 доминирует над индексом 𝑖 тогда и только тогда, когда выполняются все следующие условия:

𝑗>𝑖,
𝑝𝑗>𝑝𝑖, и
𝑞𝑗>𝑞𝑖.
Также дан массив 𝑑 длины 𝑛, где 𝑑𝑖 обозначает количество индексов, доминирующих над индексом 𝑖.

Ваша задача — построить перестановку 𝑞 чисел от 1 до 𝑛 такую, что для каждого индекса 𝑖 (1≤𝑖≤𝑛) количество индексов 𝑗, доминирующих над 𝑖, равно 𝑑𝑖.

Если такая 𝑞 существует, выведите любую подходящую. Иначе сообщите, что её не существует.

∗Перестановкой длины 𝑛 является массив, состоящий из 𝑛 различных целых чисел от 1 до 𝑛 в произвольном порядке. Например, [2,3,1,5,4] — перестановка, но [1,2,2] не перестановка (2 встречается в массиве дважды) и [1,3,4] тоже не перестановка (𝑛=3, но в массиве встречается 4).
Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число 𝑡 (1≤𝑡≤1000) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число 𝑛 (1≤𝑛≤5000).

Вторая строка каждого набора входных данных содержит 𝑛 целых чисел 𝑝1,𝑝2,…,𝑝𝑛. Гарантируется, что 𝑝 является перестановкой чисел от 1 до 𝑛.

Третья строка каждого набора входных данных содержит 𝑛 целых чисел 𝑑1,𝑑2,…,𝑑𝑛 (0≤𝑑𝑖≤𝑛).

Гарантируется, что сумма значений 𝑛 по всем наборам входных данных не превосходит 5000.

Выходные данные
Для каждого набора входных данных:

Если построить 𝑞 возможно, выведите строку из 𝑛 целых чисел 𝑞1,𝑞2,…,𝑞𝑛 — подходящую перестановку. Если существует несколько подходящих ответов, можно вывести любой из них.
Иначе выведите −1.
Пример
входные данныеСкопировать
7
3
2 3 1
1 0 0
4
3 4 1 2
2 1 1 0
5
2 3 1 4 5
2 2 1 1 0
1
1
0
5
3 1 4 2 5
1 1 1 1 0
4
3 4 2 1
1 1 1 0
8
7 6 3 1 2 5 4 8
1 1 2 2 2 1 1 0
выходные данныеСкопировать
1 2 3
-1
2 1 4 3 5
1
2 4 1 3 5
-1
1 2 4 6 5 3 7 8
Примечание
В первом наборе входных данных подходящим ответом является 𝑞=[1,2,3]:

Для 𝑖=1 имеем 𝑝1=2 и 𝑞1=1. Индекс 𝑗=2 доминирует над 𝑖=1, потому что 2>1, 𝑝2=3>𝑝1, и 𝑞2=2>𝑞1. Индекс 𝑗=3 не доминирует над 𝑖=1, потому что 𝑝3=1<𝑝1. Таким образом, над 𝑖=1 доминирует ровно 1 индекс, что совпадает с 𝑑1=1.
Для 𝑖=2 имеем 𝑝2=3 и 𝑞2=2. Единственный больший индекс — это 𝑗=3, но 𝑝3=1<𝑝2, поэтому он не доминирует. Следовательно, над 𝑖=2 доминирует 0 индексов, что совпадает с 𝑑2=0.
Для 𝑖=3 нет индексов 𝑗>3, поэтому над ним доминирует 0 индексов, что совпадает с 𝑑3=0.
Во втором наборе входных данных 𝑝=[3,4,1,2] и 𝑑=[2,1,1,0]. Рассмотрим 𝑖=2, где 𝑝2=4. Поскольку не существует индекса 𝑗>2 с 𝑝𝑗>𝑝2, ни один индекс не может доминировать над 𝑖=2. Однако массив 𝑑 требует, чтобы 𝑑2=1, что делает построение подходящей перестановки 𝑞 невозможным. Следовательно, ответ — -1.

Реши на с++ (в стиле спортивного программирования)

Answer 1

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        vector<int> p(n + 1), d(n + 1);
        for (int i = 1; i <= n; ++i) cin >> p[i];
        for (int i = 1; i <= n; ++i) cin >> d[i];

        vector<int> ord;          // индексы в порядке возрастания q
        bool ok = true;

        for (int i = n; i >= 1; --i) {
            int cntGreater = 0;
            for (int id : ord) {
                if (p[id] > p[i]) cntGreater++;
            }

            if (d[i] > cntGreater) {
                ok = false;
                break;
            }

            // Хотим вставить i так, чтобы справа было ровно d[i]
            // элементов с p[j] > p[i].
            int pos = (int)ord.size();
            int seen = 0;

            while (pos > 0 && seen < d[i]) {
                --pos;
                if (p[ord[pos]] > p[i]) seen++;
            }

            ord.insert(ord.begin() + pos, i);
        }

        if (!ok) {
            cout << -1 << '\n';
            continue;
        }

        vector<int> q(n + 1);
        for (int i = 0; i < n; ++i) {
            q[ord[i]] = i + 1;
        }

        for (int i = 1; i <= n; ++i) {
            cout << q[i] << (i == n ? '\n' : ' ');
        }
    }

    return 0;
}

Идея

Нужны только относительные значения q, а не сами числа.
Будем строить порядок индексов по возрастанию q.

Пусть мы идём справа налево: i = n, n-1, ..., 1.

Когда мы уже обработали все позиции j > i, их относительный порядок по q уже известен.
Храним его в векторе ord:

ord[0] — индекс с наименьшим q,
ord.back() — индекс с наибольшим q.

Теперь нужно вставить индекс i в ord.

Если вставить i в некоторую позицию, то:

справа от него в ord будут стоять ровно те j > i, для которых q[j] > q[i],
среди них доминируют только те, у кого ещё и p[j] > p[i].

Значит, нам надо выбрать позицию вставки так, чтобы справа оказалось ровно d[i] элементов с p[j] > p[i].

Почему это всегда можно сделать?

Пусть среди уже обработанных элементов количество индексов с p[j] > p[i] равно cnt.

Если d[i] > cnt, ответа не существует.
Иначе позиция всегда найдётся:

Если двигать место вставки справа налево, то число элементов p[j] > p[i] справа:

начинается с 0,
заканчивается на cnt,
увеличивается на 1 каждый раз, когда мы пересекаем элемент с p[j] > p[i].

Значит, можно получить любое значение от 0 до cnt.

Сложность

Из-за вставок в вектор и проходов по нему:

O(n^2) на тест,
суммарно по условию Σn ≤ 5000, так что этого более чем достаточно.

Если хочешь, я могу ещё написать короткое доказательство корректности в формате, удобном для вставки в разбор.

Дана перестановка 𝑝∗ чисел от 1 до 𝑛. Для произ...

Вопрос

Мысль

Ответ

Идея

Почему это всегда можно сделать?

Сложность

Поделиться этим Q&A