Містичний свап#13122

Містичний свап (Розбір)

Розв'язок

Початково перестановка була p=(1,2,\ldots,n). Після обміну позицій i<j число опинилося на позиції , а число — на позиції .

Число утворює j-i інверсій з елементами на позиціях i+1,\ldots,j. Крім того, число утворює ще j-i-1 інверсій з елементами на позиціях i+1,\ldots,j-1. Інших інверсій немає, тому запит до всього масиву поверне

cnt=2(j-i)-1.

Звідси знайдемо відстань між позиціями:

j-i=\frac{cnt+1}{2}.

Тепер знайдемо . На префіксах з r\le i інверсій немає. Натомість префікс [1,i+1] уже містить інверсію між елементами на позиціях та i+1. Оскільки при збільшенні префікса кількість інверсій не зменшується, предикат «кількість інверсій на більша за нуль» є монотонним.

Бінарним пошуком знайдемо найменше , для якого цей предикат істинний. Тоді r=i+1, тобто i=r-1. Другу позицію отримаємо за формулою

j=i+\frac{cnt+1}{2}.

Спочатку робимо один запит до , після чого виконуємо бінарний пошук. Усього потрібно не більш ніж

1+\lceil\log_2 n\rceil\le15

запитів, оскільки n\le10^4.

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

Складність

Використовуємо O(\log n) запитів і O(\log n) часу на один набір даних, додаткова пам'ять .

Реалізація C++17

#include <bits/stdc++.h>
using namespace std;

int ask(int l, int r) {
    cout << "? " << l << ' ' << r << endl;
    int x;
    if (!(cin >> x) || x == -1) exit(0);
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (!(cin >> t) || t == -1) return 0;

    while (t--) {
        int n;
        if (!(cin >> n) || n == -1) return 0;

        int cnt = ask(1, n);
        int l = 0, r = n;

        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (ask(1, mid) > 0) r = mid;
            else l = mid;
        }

        int i = l;
        int j = i + (cnt + 1) / 2;
        cout << "! " << i << ' ' << j << endl;
    }
}