4-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача B. MEXI

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

512 мегабайт

Аза решал следующию задачу от Нархана: Вам задан массив $a$, состоящий из $n$ целых неотрицательных чисел. Назовем разделение массива $a$ на $k$ отрезков $(l_1, r_1), \ldots, (l_k, r_k)$ $x$- хорошим, если выполняются следующие условия:

• Каждый элемент массива $a$ принадлежит ровно одному отрезку.
• Для каждого $1 <= i <= k$, $MEX$ чисел $(a_{l_i}, \ldots, a_{r_i})$ был меньше или равен $x$.

В этой задаче $MEX$ некоторого массива — это минимальное неотрицательное целое число, которое не содержится в этом массиве. Например:

• $MEX$ для $[2,2,1]$ равен $0$, поскольку $0$ не принадлежит массиву.
• $MEX$ для $[3,1,0,1]$ равен $2$, поскольку $0$ и $1$ принадлежат массиву, а $2$ — нет.
• $MEX$ для $[0,3,1,2]$ равен $4$, поскольку $0$, $1$, $2$ и $3$ принадлежат массиву, а $4$ — нет.

Размером $x$ хорошего разделение является количество отрезков на которое оно было разделено — то есть $k$. Вам нужно для каждого целого числа $x$ от $0$ до $n-1$ вывести минимальный возможный размер $x$ хорошего разделения, если данное разделение невыполнимо выведите $-1$.

Формат входного файла

Первая строка содержит одно целое число — $n$ ($1 <= n <= 10^6$). Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ $(0 <= a_i <= 10^6)$ — массив $a$.

Формат выходного файла

Выведите $n$ целых чисел, где $i$-е число — это минимальный возможный размер $x$ хорошего разделения при $x = i-1$, если данное разделение невыполнимо выведите $-1$.

Примеры:

Вход

4
0 1 0 2

Ответ

-1 3 2 1

Вход

1
2

Ответ

1

Замечание

В первом примере:

• при $x = 0$, не существует хорошего разделения массива, поэтому выводим $-1$.
• при $x = 1$, делим на $3$ отрезка: [$0$],[$1$],[$0,2$].
• при $x = 2$, делим на $2$ отрезка: [$0,1$], [$0,2$].
• при $x = 3$, один отрезок - сам массив [$0,1,0,2$].

( Dimash Tursynbai )

Комментарий/решение

Алгоритм:

Создаем множество set_nums, в котором будем хранить все уникальные элементы массива a.

Находим минимальный элемент min_a в массиве a.

Если min_a равен 0, то выводим 1, так как разделение на отрезки единственное и состоит из всех элементов массива.

Иначе, если 0 не содержится в set_nums, то выводим 0, так как невозможно построить хорошее разделение.

Иначе, создаем переменную cur, равную минимальному элементу min_a, и удаляем его из множества set_nums.

Запускаем цикл от 1 до n+1:

Если cur содержится в set_nums, то удаляем его из множества и увеличиваем cur на 1.

Иначе, выводим текущее значение цикла и завершаем программу.

Блок-схема:

+-------------------------+

| Создать множество set |

| для уникальных элементов|

| массива a |

+-------------------------+

|

|

|

v

+----------------+

| Найти min_a в a |

+----------------+

|

|

|

v

+-------------------+

| Если min_a = 0, |

| вывести 1 и выйти|

+-------------------+

|

|

|

v

+---------------+

| Если 0 нет в |

| set_nums, |

| вывести 0 и |

| выйти |

+---------------+

|

|

|

v

+-------------------+

| Создать cur = min_a|

| и удалить его из |

| set_nums |

+-------------------+

|

|

|

v

+---------------+

| Для i от 1 до n+1|

+---------------+

|

|

|

v

+--------------------------+

| Если cur в set_nums, |

| удалить его и увеличить |

| cur на 1 |

+--------------------------+

|

|

+-----------+-------+

| | |

| v |

| Если cur не в |

| set_nums, вывести i |

| и завершить программу|

| |

v v

Алгоритм решения:

Создаем массив a[1000001] и инициализируем его нулями.

Считываем массив чисел входного файла и для каждого числа i, устанавливаем a[i] равным единице.

Выполняем проход по a, начиная с 0, и считаем количество пройденных нулей (count) и единиц (ones).

Если count + ones = n, где n - размер массива, то выводим 1, иначе выводим 2.

Пояснения:

a[i] будет равно 1, если число i содержится в массиве nums.

count - количество нулей, которые мы прошли в массиве a.

ones - количество единиц, которые мы прошли в массиве a.

Если мы прошли все элементы массива a и count + ones не равно n, то это означает, что есть число, которое не содержится в массиве. Поэтому для любого числа i от 0 до n мы можем создать разделение, в котором i не встречается, и количество отрезков в этом разделении будет равно i + 1.

Временная сложность алгоритма: O(n).

Блок-схема алгоритма:

+--------+

| Старт |

+--------+

|

v

+-----------------+

| Инициализация |

+-----------------+

|

v

+-----------------+

| Считать массив |

+-----------------+

|

v

+-----------------+

| Обработка |

+-----------------+

|

v

+-----------------+

| Вывод |

+-----------------+

|

v

+--------+

| Финиш |

+--------+

Код на языке C++:

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

cin >> n;

vector<int> nums(n);

for (int i = 0; i < n; i++) {

cin >> nums[i];

}

vector<int> a(1000001, 0);

for (int i = 0; i < n; i++) {

a[nums[i]] = 1;

}

int count = 0, ones = 0;

for (int i = 0; i <= n; i++) {

if (a[i] == 0) {

count++;

} else {

ones++;

}

if (count + ones == n) {

cout << "1\n";

return 0;

}

}

for (int i = 0; i < n; i++) {

if (nums[i] >= n) {

cout << "2\n";

return 0;

}

}

for (int i = 0; i < n; i++) {

if (a[i] == 0) {

cout << i + 1 << "\n";

return 0;

}

}

return 0;

}

Что за позер, сейчас бы ChatGPT использовать ради того, чтоб дать свой коммент? Удали, или если у тебя есть весомая цель чтоб публиковать это, оборачивай в читаемый и спойлер код.

решение на python

показать/скрыть код

from collections import defaultdict
where=defaultdict(list)
n=int(input())
a=list(map(int,input().split()))
for i in range(n):where[a[i]].append(i+1)
index_lim=n
fenw_max=[0]*(n+1)
def pref_max(p):
	res=0
	while p>0:res=max(res,fenw_max[p]);p-=p&-p
	return res
def update_max(p,x):
	while p<=n:fenw_max[p]=max(fenw_max[p],x);p+=p&-p
def add(x):
	prv=0
	for pos in where[x]:update_max(prv+1,pos);prv=pos
	global index_lim;index_lim=min(index_lim,prv)
for x in range(n):
	add(x);i,ans=1,0
	while i<=n:
		if i>index_lim:j=n+1
		else:j=pref_max(i)
		ans+=1
		if j==i:ans=-1;break
		i=j
	print(ans,end=' 'if x!=n-1 else'\n')