QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #607034 | #8939. Permutation | lllei# | WA | 2ms | 3688kb | C++20 | 1.7kb | 2024-10-03 13:42:47 | 2024-10-03 13:42:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >>n;
auto query = [&](int l, int r) {
cout << "? " << l << ' ' << r << endl;
int p;
cin >> p;
return p;
};
auto answer = [&](int x) {
cout << "! " << x << endl;
};
auto div = [&](auto &&self, int l, int r, int p) -> void {
if (r - l + 1 == 1) {
answer(l);
return;
}
if (r - l + 1 == 2) {
answer(l + r - p);
return;
}
int len = r - l + 1;
int t = ceil((r - l + 1) * 0.618);
if (l + t - 1 >= p) {
int nxtp = query(l, l + t - 1);
if (nxtp == p) {
self(self, l, l + t - 1, p);
} else {
if (len - t == 1) {
answer(r);
return;
}
int p1 = query(r - (len - t) + 1, r);
self(self, r - (len - t) + 1, r, p1);
}
} else {
int nxtp = query(r - t + 1, r);
if (nxtp == p) {
self(self, r - t + 1, r, p);
} else {
if (len - t == 1) {
answer(l);
return;
}
int p1 = query(l, l + (len - t) - 1);
self(self, l, l + (len - t) - 1, p1);
}
}
};
int p = query(1, n);
div(div, 1, n, p);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
input:
3 5 3 3 2 6 6 3 1 4 3 2
output:
? 1 5 ? 1 4 ? 1 3 ! 4 ? 1 6 ? 3 6 ? 1 2 ! 2 ? 1 4 ? 1 3 ! 4
result:
ok Correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3688kb
input:
10000 10 2 2 2 2 3 10 10 10 10 7 10 5 5 1 6 10 4 4 4 4 4
output:
? 1 10 ? 1 7 ? 1 5 ? 1 4 ? 1 3 ! 4 ? 1 10 ? 4 10 ? 6 10 ? 7 10 ! 6 ? 1 10 ? 1 7 ? 1 5 ? 6 7 ! 7 ? 1 10 ? 1 7 ? 1 5 ? 1 4 ? 2 4 ? 3 4
result:
wrong answer Too many queries , n = 10 , now_q 6 (test case 4)