Що дає один запит. Ключ до задачі — зрозуміти, що насправді питає запит. Візьмемо два різні індекси і та побудуємо масив , у якому 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 із самим собою, тож не дають нічого. Оскільки — перестановка, рівності не буває, і рівно одна з двох перевірок спрацьовує:
Іншими словами, транспозиція в масиві — це запитання «хто з двох більший?».
Більше того, у масиві можна одночасно розмістити багато неперетинних транспозицій, і всі відповідні порівняння виконаються незалежно за один запит. Отже один запит — це цілий шар паралельних компараторів.
Переформулювання. Ми маємо відсортувати невідомих значень, маючи право на кожному кроці виконати довільний набір неперетинних порівнянь, а мінімізуємо кількість кроків. Це рівно задача про сортувальну мережу мінімальної глибини, і тут працює класика — бітонне сортування Бетчера.
Нагадаємо схему. Підтримуємо масив «дротів» , де b_h — індекс позиції, що зараз лежить на дроті . Зовнішній цикл подвоює довжину блоку: i = 2, 4, \ldots, n; внутрішній цикл іде j = i/2, i/4, \ldots, 1. На кроці порівнюються всі пари дротів (h,\ h + j) з h \wedge j = 0, а напрям сортування визначається бітом у номері дроту:
Пари в межах одного кроку не перетинаються, тож увесь крок — це один запит. Отримавши , для кожної пари дивимось на c_{b_{h+j}}: якщо порядок не збігається з потрібним напрямом — міняємо b_h і b_{h+j} місцями.
Скільки запитів. Кроків рівно
для n = 1024 це \frac{10 \cdot 11}{2} = 55 — саме та межа, за якою дають повний бал. Саме тому в умові гарантовано, що — степінь двійки: бітонна мережа означена для таких довжин без жодних доповнень.
Відповідь. Наприкінці дріт містить індекс позиції, значення якої є (h+1)-м за зростанням, тобто p_{b_h} = h + 1. Лишається розставити ці значення й вивести перестановку.
Не забудьте про flush після кожного запиту — задача інтерактивна, і без скидання буфера програма зависне.