| Codeforces Round 1012 (Div. 2) |
|---|
| Закончено |
В большом королевстве есть бесконечный обеденный зал. Его можно представить как множество клеток ($$$x, y$$$), где $$$x$$$ и $$$y$$$ — неотрицательные целые числа. В зале находится бесконечное количество столов. Каждый стол занимает четыре клетки ($$$3x + 1, 3y + 1$$$), ($$$3x + 1, 3y + 2$$$), ($$$3x + 2, 3y + 1$$$), ($$$3x + 2, 3y + 2$$$), где $$$x$$$ и $$$y$$$ — произвольные неотрицательные целые числа. Все клетки, которые не принадлежат ни одному из столов, являются коридорами.
В зал приходят $$$n$$$ гостей по одному. Каждый гость появляется в клетке ($$$0, 0$$$) и хочет добраться до клетки со столом. За один шаг они могут перемещаться в любую соседнюю по стороне клетку, являющуюся коридором, а последним шагом они должны переместиться в соседнюю по стороне свободную клетку со столом. Они занимают выбранную клетку стола, и ни один другой гость не может туда переместиться.
У каждого гостя есть характеристика $$$t_i$$$, которая может быть равна $$$0$$$ или $$$1$$$. Они входят в зал по порядку, начиная движение из клетки $$$(0, 0)$$$. Если $$$t_i=1$$$, то $$$i$$$-й гость идет к ближайшей клетке со столом. Если же $$$t_i=0$$$, то он идет к ближайшей клетке со столом, которая принадлежит полностью незанятому столу. Обратите внимание, что другие гости могут выбрать тот же стол позже.
Расстояние определяется как наименьшее количество шагов, необходимых для достижения клетки со столом. Если есть несколько клеток со столом на одном расстоянии, гости выбирают клетку с наименьшим $$$x$$$, а если и таких клеток несколько, то они выбирают среди них клетку с наименьшим $$$y$$$.
Для каждого гостя найдите клетку со столом, на которую они сядут.
В первой строке задано единственное число $$$q$$$ ($$$1 \leq q \leq 5000$$$) — количество наборов входных данных. Затем идет их описание.
В первой строке каждого набора входных данных задано единственное число $$$n$$$ ($$$1 \leq n \leq 50\,000$$$) — количество гостей.
Во второй строке каждого набора входных данных записаны $$$n$$$ чисел $$$t_1, t_2, \ldots, t_n$$$ ($$$t_i \in \{0, 1\}$$$) — характеристики гостей.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$50\,000$$$.
Для каждого набора входных данных выведите $$$n$$$ строк — для каждого гостя клетку, куда он сел.
260 1 1 0 0 151 0 0 1 1
1 1 1 2 2 1 1 4 4 1 1 5 1 1 1 4 4 1 1 2 2 1
Рассмотрим первый набор входных данных:
У первого гостя расстояние до клетки ($$$1, 1$$$) равно $$$2$$$, поэтому он садится за него.
У второго гостя расстояние до клетки ($$$1, 2$$$) равно $$$3$$$, как и до клетки ($$$2, 1$$$), но у первого варианта первая координата меньше, поэтому он выберет его.
У третьего гостя расстояние до клетки ($$$2, 1$$$) равно $$$3$$$, поэтому он выберет её.
У четвертого гостя расстояние до клетки ($$$1, 4$$$) равно $$$5$$$, он выберет её.
У пятого гостя расстояние до клетки ($$$4, 1$$$) равно $$$5$$$.
У шестого гостя расстояние до клетки ($$$1, 5$$$) равно $$$6$$$, как и до клетки ($$$2, 2$$$), но так как первая координата меньше, то он выберет первый вариант.
