QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#684497 | #8939. Permutation | real_sigma_team# | WA | 1ms | 3624kb | C++23 | 1.0kb | 2024-10-28 13:55:45 | 2024-10-28 13:55:46 |
Judging History
answer
#include<bits/stdc++.h>
int main() {
// std::cin.tie(nullptr)->sync_with_stdio(false);
int tests;
std::cin >> tests;
while (tests--) {
int n;
std::cin >> n;
auto rec = [&](auto rec, int l, int r, int p) -> void {
if (l == r) {
std::cout << "! " << l << std::endl;
return;
}
if (p == -1) {
std::cout << "? " << l << ' ' << r << std::endl;
std::cin >> p;
}
if (r - l == 1) {
if (l == p) std::cout << "! " << r << std::endl;
else std::cout << "! " << l << std::endl;
return;
}
double phi = 2 / (sqrt(5) + 1);
int len = (r - l + 1) * phi;
int m1 = r - len;
int m2 = l + len;
if (p > m1) {
std::cout << "? " << m1 + 1 << ' ' << r << std::endl;
int shq;
std::cin >> shq;
if (shq == p) rec(rec, m1 + 1, r, p);
else rec(rec, l, m1, -1);
} else {
std::cout << "? " << l << ' ' << m2 << std::endl;
int shq;
std::cin >> shq;
if (shq == p) rec(rec, l, m2, p);
else rec(rec, m2 + 1, r, -1);
}
};
rec(rec, 1, n, -1);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3624kb
input:
3 5 3 3 3 6 6 5 3
output:
? 1 5 ? 3 5 ? 3 4 ! 4 ? 1 6 ? 4 6 ? 1 3 ? 3 3
result:
wrong answer Integer 3 violates the range [4, 6] (test case 2)