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

Есеп В. MEXI

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

1.5 seconds

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

512 megabytes

Нархан Аза-ға келесі есепті ұсынды: Сізге мөлшері $n$ болатын бүтін сандардан тұратын $a$ массиві берілген. $a$ массивін $k$ бөлікке $(l_1, r_1), \ldots, (l_k, r_k)$ бөлуін $x$-жақсы бөлініс деп атаймыз егер келесі шарттар орындалса:

• $a$ массивының кез-келген элементі дәл бір бөлікте жатады.
• Кез келген $1 <= i <= k$ үшін, $(a_{l_i}, \ldots, a_{r_i})$ сандарының $MEX$і $x$-тен кіші немесе тең болады.

Осы есепте сандар жиынтығының $MEX$і — сол жиынтықта кездеспейтін ең кіші теріс емес бүтін сан. Мысалы:

• $[2,2,1]$ $MEX$i $0$, себебі $0$ массивте кездеспейді.
• $[3,1,0,1]$ $MEX$і $2$, себебі $0$ жәңе $1$ массивте кездеседі, ал $2$ — жоқ.
• $[0,3,1,2]$ $MEX$і $4$, себебі $0$, $1$, $2$ жәңе $3$ массивте кездеседі, ал $4$ — жоқ.

$x$ жақсы бөліністің өлшемі деп қанша бөлікке бөлуін атаймыз, басқаша айтқанда $k$ саны. Әр бүтін $0$-ден $n-1$-ге дейінгі $x$ санына ең кішкентай мүмкін болатың $x$ жақсы бөліністің өлшемін шығарыңыз, егер сондай бөлініс болмаса $-1$ шыгарыңыз.

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

Бірінші жолда бір бүтін сан — $n$ ($1 <= n <= 10^6$) берілген. Екінші жолда $n$ бүтін сандар $a_1, a_2, \ldots, a_n$ $(0 <= a_i <= 10^6)$ — $a$ массиві берілген.

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

$n$ бүтін санды шығарыңыз, мұнда $i$-ші сан ол $x = i-1$ кездегі ең кішкентай мүмкін болатың $x$ жақсы бөліністің өлшемі. Олай бөлу мүмкін болмаса $-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')