Solution
Initially, the permutation was p=(1,2,\ldots,n). After swapping positions i<j, the number moved to position , and the number moved to position .
The number forms j-i inversions with the elements at positions i+1,\ldots,j. Additionally, the number forms another j-i-1 inversions with the elements at positions i+1,\ldots,j-1. There are no other inversions, so querying the entire array returns
Hence, we can find the distance between the two positions:
Now we need to find . For every prefix with r\le i, there are no inversions. However, the prefix [1,i+1] already contains an inversion between the elements at positions and i+1. Since the number of inversions cannot decrease when extending a prefix, the predicate "the number of inversions in is positive" is monotonic.
Using binary search, we find the smallest for which this predicate is true. Then r=i+1, so i=r-1. The second position can be found using
First, we make one query for , then perform binary search. The total number of queries does not exceed
since n\le10^4.
We must flush the output buffer after every query and final answer. After a correct answer, the interactor immediately sends for the next test case without any additional acknowledgement. If we receive or reach the end of the input stream, we must terminate the program immediately.
Complexity
We use O(\log n) queries and O(\log n) time per test case, with auxiliary space.
C++17 Implementation
#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;
}
}