Codeforces Round 948 (Div. 2) |
---|
Закончено |
Это интерактивная задача.
Вам дано целое число $$$n$$$.
Жюри загадало ориентированный граф с $$$n$$$ вершинами (пронумерованными от $$$1$$$ до $$$n$$$) и с некоторым количеством рёбер. Дополнительно известно, что:
Вы хотите покрасить каждую вершину графа либо в белый, либо в чёрный цвет так, чтобы для любых двух вершин $$$i$$$ и $$$j$$$ ($$$1 \le i < j \le n$$$) одного цвета вершина $$$i$$$ была достижима из вершины $$$j$$$.
Для этого вы можете делать запросы следующего вида:
Найдите любую подходящую раскраску вершин графа за не более чем $$$2 \cdot n$$$ запросов. Можно доказать, что такая раскраска всегда существует.
Примечание: интерактор не является адаптивным, то есть граф фиксируется до выполнения каких-либо запросов.
$$$^\dagger$$$ Вершина $$$a$$$ достижима из вершины $$$b$$$ если в графе существует путь из вершины $$$b$$$ в вершину $$$a$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество вершин в графе.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$1000$$$.
Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.
Для формирования запроса выведите «? i j» без кавычек ($$$1 \le i < j \le n$$$). Если вершина $$$i$$$ достижима из вершины $$$j$$$, вы получите в ответ YES. Иначе, вы получите в ответ NO.
Если вместо ответа или допустимого значения $$$n$$$ вы получите целое число $$$-1$$$, то это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неверный ответ на предыдущем наборе входных данных. При получении вердикта «Неправильный ответ» ваша программа должна немедленно завершиться. В противном случае можно получить произвольный вердикт, поскольку решение будет продолжать считывать данные из закрытого потока.
Когда вы будете готовы дать окончательный ответ, выведите «! $$$c_1 \ c_2 \ \ldots \ c_n$$$» без кавычек — раскраска вершин графа, где $$$c_i = 0$$$, если вершина чёрная, и $$$c_i = 1$$$, если вершина белая. После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Для взлома используйте следующий формат:
Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 100$$$, $$$0 \le m \le \frac{n\cdot(n - 1)}{2}$$$) — количество вершин и рёбер в графе.
Следующие $$$m$$$ строк должны содержать два числа $$$a$$$ и $$$b$$$ ($$$1 \le b < a \le n$$$), означающие, что в графе присутствует ребро $$$a \rightarrow b$$$. Граф должен удовлетворять условиям выше.
Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$1000$$$.
2 4 YES YES YES NO NO NO 5
? 1 2 ? 2 3 ? 1 3 ? 1 4 ? 2 4 ? 3 4 ! 0 0 0 1 ! 1 1 0 1 0
Граф в первом примере:
Граф во втором примере:
Взаимодействие происходит следующим образом:
Решение | Жюри | Объяснение |
2 | Есть $$$2$$$ набора входных данных. | |
4 | В первом наборе входных данных загадан граф с $$$4$$$-мя вершинами. | |
? 1 2 | YES | Решение спрашивает, достижима ли вершина $$$1$$$ из вершины $$$2$$$, жюри отвечает YES. |
? 2 3 | YES | Решение спрашивает, достижима ли вершина $$$2$$$ из вершины $$$3$$$, жюри отвечает YES. |
? 1 3 | YES | Решение спрашивает, достижима ли вершина $$$1$$$ из вершины $$$3$$$, жюри отвечает YES. |
? 1 4 | NO | Решение спрашивает, достижима ли вершина $$$1$$$ из вершины $$$4$$$, жюри отвечает NO. |
? 2 4 | NO | Решение спрашивает, достижима ли вершина $$$2$$$ из вершины $$$4$$$, жюри отвечает NO. |
? 3 4 | NO | Решение спрашивает, достижима ли вершина $$$3$$$ из вершины $$$4$$$, жюри отвечает NO. |
! 0 0 0 1 | Решение каким-то образом определило, что такая раскраска подходит, и выводит её. Поскольку ответ правильный, жюри переходит к следующему набору входных данных. | |
1 | Во втором наборе входных данных загадан граф с $$$5$$$-ю вершинами. | |
! 1 1 0 1 0 | Решение каким-то образом определило, что такая раскраска подходит, и выводит её. Поскольку ответ верен и наборов входных данных больше нет, жюри и решение завершаются. |
Обратите внимание, что пустые строки во входных и выходных данных примера сделаны для наглядности и не встречаются в реальном взаимодействии.
Название |
---|