Вгадайте перестановку#203

Вгадайте перестановку (Розбір)

Що дає один запит. Ключ до задачі — зрозуміти, що насправді питає запит. Візьмемо два різні індекси і та побудуємо масив , у якому a_u = v, a_v = u, а решта позицій вказують самі на себе (a_i = i).

Розберемо, що порахує журі. Позиція i = u дає a_u = v і перевірку p_v > p_u; у разі успіху збільшується c_v. Позиція i = v дає симетричну перевірку p_u > p_v і збільшує c_u. Позиції з a_i = i порівнюють p_i із самим собою, тож не дають нічого. Оскільки — перестановка, рівності не буває, і рівно одна з двох перевірок спрацьовує:

c_v = 1 \iff p_v > p_u.

Іншими словами, транспозиція в масиві — це запитання «хто з двох більший?».

Більше того, у масиві можна одночасно розмістити багато неперетинних транспозицій, і всі відповідні порівняння виконаються незалежно за один запит. Отже один запит — це цілий шар паралельних компараторів.

Переформулювання. Ми маємо відсортувати невідомих значень, маючи право на кожному кроці виконати довільний набір неперетинних порівнянь, а мінімізуємо кількість кроків. Це рівно задача про сортувальну мережу мінімальної глибини, і тут працює класика — бітонне сортування Бетчера.

Нагадаємо схему. Підтримуємо масив «дротів» , де b_h — індекс позиції, що зараз лежить на дроті . Зовнішній цикл подвоює довжину блоку: i = 2, 4, \ldots, n; внутрішній цикл іде j = i/2, i/4, \ldots, 1. На кроці порівнюються всі пари дротів (h,\ h + j) з h \wedge j = 0, а напрям сортування визначається бітом у номері дроту:

\text{зростання, якщо } (h \wedge i) = 0, \quad \text{спадання інакше.}

Пари в межах одного кроку не перетинаються, тож увесь крок — це один запит. Отримавши , для кожної пари дивимось на c_{b_{h+j}}: якщо порядок не збігається з потрібним напрямом — міняємо b_h і b_{h+j} місцями.

Скільки запитів. Кроків рівно

\sum_{k=1}^{\log_2 n} k \;=\; \frac{\log_2 n\,(\log_2 n + 1)}{2},

для n = 1024 це \frac{10 \cdot 11}{2} = 55 — саме та межа, за якою дають повний бал. Саме тому в умові гарантовано, що — степінь двійки: бітонна мережа означена для таких довжин без жодних доповнень.

Відповідь. Наприкінці дріт містить індекс позиції, значення якої є (h+1)-м за зростанням, тобто p_{b_h} = h + 1. Лишається розставити ці значення й вивести перестановку.

Не забудьте про flush після кожного запиту — задача інтерактивна, і без скидання буфера програма зависне.