Олимпиадный тренинг

Задача . C. Мастер игры


Задача

Темы: графы два указателя дп жадные алгоритмы поиск в глубину и подобное Структуры данных *1700

\(n\) игроков играют в игру.

В игре есть две различные игровые карты. Для каждого игрока мы знаем его силу на каждой карте. Когда два игрока сражаются на определенной карте, всегда побеждает игрок с большей силой на этой карте. Нет двух игроков с одинаковой силой на одной и той же карте.

Вы — мастер этой игры, и хотите организовать турнир. Всего будет проведено \(n-1\) боев. Пока в турнире участвует более одного игрока, выберите любую карту и любых двух из оставшихся игроков, которые будут сражаться на ней. Игрок, который проиграет, выбывает из турнира.

В итоге останется ровно один игрок, и он объявляется победителем турнира. Для каждого игрока определите, может ли он выиграть турнир.

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \leq n \leq 10^5\)) — количество игроков.

Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\), \(a_i \neq a_j\) для \(i \neq j\)), где \(a_i\) — сила \(i\)-го игрока на первой карте.

Третья строка каждого набора входных данных содержит \(n\) целых чисел \(b_1, b_2, \dots, b_n\) (\(1 \leq b_i \leq 10^9\), \(b_i \neq b_j\) для \(i \neq j\)), где \(b_i\) — сила \(i\)-го игрока на второй карте.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(10^5\).

Выходные данные

Для каждого набора входных данных выведите строку длины \(n\). \(i\)-й символ должен быть «1», если \(i\)-й игрок может выиграть турнир, или «0» в противном случае.

Примечание

В первом наборе входных данных \(4\)-й игрок обыграет любого другого игрока в любой игре, поэтому он обязательно выиграет турнир.

Во втором наборе входных данных каждый может стать победителем.

В третьем наборе входных данных есть только один игрок. Очевидно, что он выиграет турнир.


Примеры
№Входные данныеВыходные данные
1 3
4
1 2 3 4
1 2 3 4
4
11 12 20 21
44 22 11 30
1
1000000000
1000000000 
0001
1111
1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет