#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n;
cin >> n;
if(n == 2)
{
cout << "? 1" << endl;
int reply;
cin >> reply;
cout << "? 2" << endl;
cin >> reply;
reply = 1 - reply;
cout << "= " << reply + 1 << endl;
return;
}
int reply;
cout << "? " << (3 * n + 3) / 4 << endl;
cin >> reply;
cout << "? " << (n + 3) / 4 << endl;
cin >> reply;
set<int> already_replied;
already_replied.insert((3 * n + 3) / 4);
already_replied.insert((n + 3) / 4);
int value = ((3 * n + 3) / 4) - ((n + 3) / 4);
int to_check = value;
if(reply == 0)
{
to_check += (value + 1) / 2;
}
else
{
to_check -= (value + 1) / 2;
}
// cout << "value = " << value << ", to_check = " << to_check << endl;
int queries = 2;
int current_value = (n + 3) / 4;
int final_answer = (reply == 0) ? n : ((3 * n + 3) / 4 - (n + 3) / 4);
while(true)
{
queries++;
if(queries == 65)
{
break;
}
// cout << "current to check is: " << to_check << endl;
int to_the_left = current_value - to_check;
int to_the_right = current_value + to_check;
if(already_replied.count(to_the_left) || to_the_left <= 0)
{
if(already_replied.count(to_the_right) || to_the_right > n)
{
for(int i = 1; i <= n; i++)
{
if(!already_replied.count(i))
{
cout << "? " << i << endl;
cin >> reply;
current_value = i;
already_replied.insert(i);
break;
}
}
}
else
{
cout << "? " << to_the_right << endl;
already_replied.insert(to_the_right);
cin >> reply;
value = (value + 1) / 2;
current_value = to_the_right;
if(reply == 0)
{
to_check += value / 2;
}
else
{
final_answer = to_check;
to_check -= value / 2;
}
}
}
else
{
cout << "? " << to_the_left << endl;
already_replied.insert(to_the_left);
cin >> reply;
value = (value + 1) / 2;
current_value = to_the_left;
if(reply == 0)
{
to_check += value / 2;
}
else
{
final_answer = to_check;
to_check -= value / 2;
}
}
}
cout << "= " << final_answer << endl;
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 2 |
Correct |
1 ms |
208 KB |
OK (49 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (10 queries) |
| 4 |
Correct |
1 ms |
320 KB |
OK (26 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (23 queries) |
| 6 |
Correct |
1 ms |
208 KB |
OK (56 queries) |
| 7 |
Correct |
1 ms |
208 KB |
OK (52 queries) |
| 8 |
Correct |
2 ms |
208 KB |
OK (43 queries) |
| 9 |
Correct |
1 ms |
208 KB |
OK (46 queries) |
| 10 |
Correct |
1 ms |
208 KB |
OK (11 queries) |
| 11 |
Incorrect |
1 ms |
320 KB |
Wrong guess |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 2 |
Correct |
1 ms |
208 KB |
OK (49 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (10 queries) |
| 4 |
Correct |
1 ms |
320 KB |
OK (26 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (23 queries) |
| 6 |
Correct |
1 ms |
208 KB |
OK (56 queries) |
| 7 |
Correct |
1 ms |
208 KB |
OK (52 queries) |
| 8 |
Correct |
2 ms |
208 KB |
OK (43 queries) |
| 9 |
Correct |
1 ms |
208 KB |
OK (46 queries) |
| 10 |
Correct |
1 ms |
208 KB |
OK (11 queries) |
| 11 |
Incorrect |
1 ms |
320 KB |
Wrong guess |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 2 |
Correct |
1 ms |
208 KB |
OK (49 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (10 queries) |
| 4 |
Correct |
1 ms |
320 KB |
OK (26 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (23 queries) |
| 6 |
Correct |
1 ms |
208 KB |
OK (56 queries) |
| 7 |
Correct |
1 ms |
208 KB |
OK (52 queries) |
| 8 |
Correct |
2 ms |
208 KB |
OK (43 queries) |
| 9 |
Correct |
1 ms |
208 KB |
OK (46 queries) |
| 10 |
Correct |
1 ms |
208 KB |
OK (11 queries) |
| 11 |
Incorrect |
1 ms |
320 KB |
Wrong guess |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 2 |
Correct |
1 ms |
208 KB |
OK (49 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (10 queries) |
| 4 |
Correct |
1 ms |
320 KB |
OK (26 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (23 queries) |
| 6 |
Correct |
1 ms |
208 KB |
OK (56 queries) |
| 7 |
Correct |
1 ms |
208 KB |
OK (52 queries) |
| 8 |
Correct |
2 ms |
208 KB |
OK (43 queries) |
| 9 |
Correct |
1 ms |
208 KB |
OK (46 queries) |
| 10 |
Correct |
1 ms |
208 KB |
OK (11 queries) |
| 11 |
Incorrect |
1 ms |
320 KB |
Wrong guess |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
OK (7 queries) |
| 2 |
Correct |
1 ms |
208 KB |
OK (49 queries) |
| 3 |
Correct |
0 ms |
208 KB |
OK (10 queries) |
| 4 |
Correct |
1 ms |
320 KB |
OK (26 queries) |
| 5 |
Correct |
1 ms |
208 KB |
OK (23 queries) |
| 6 |
Correct |
1 ms |
208 KB |
OK (56 queries) |
| 7 |
Correct |
1 ms |
208 KB |
OK (52 queries) |
| 8 |
Correct |
2 ms |
208 KB |
OK (43 queries) |
| 9 |
Correct |
1 ms |
208 KB |
OK (46 queries) |
| 10 |
Correct |
1 ms |
208 KB |
OK (11 queries) |
| 11 |
Incorrect |
1 ms |
320 KB |
Wrong guess |
| 12 |
Halted |
0 ms |
0 KB |
- |
