QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #588428 | #8939. Permutation | Tobo | WA | 7ms | 3644kb | C++20 | 1.6kb | 2024-09-25 11:00:31 | 2024-09-25 11:42:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int l = 1, r = n, mid, len, lst, res;
cout << "? " << 1 << ' ' << n << endl;
cin >> lst;
while (l + 1 < r)
{
len = r - l + 1;
mid = l + floor(0.618034 * len);
if (lst <= mid)
{
cout << "? " << l << ' ' << mid << endl;
cin >> res;
if (lst == res)
r = mid;
else
{
l = mid + 1;
if (l < r)
{
cout << "? " << l << ' ' << r << endl;
cin >> lst;
}
}
}
else
{
mid = r - floor(0.618034 * len);
cout << "? " << mid << ' ' << r << endl;
cin >> res;
if (lst == res)
l = mid;
else
{
r = mid - 1;
if (l < r)
{
cout << "? " << l << ' ' << r << endl;
cin >> lst;
}
}
}
}
if (l == r or lst == l)
cout << "! " << r << endl;
else
cout << "! " << l << endl;
}
}
/*
6
1 6 4 2 3 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
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: 7ms
memory: 3592kb
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)