#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int N;
int fix(int dir, int X) {
return (dir == 1 ? X : N + 1 - X);
}
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(0, 1);
int max_end[30];
int mid_game(int lt, int rt, int prv) {
if (lt > rt) {
swap(lt, rt);
}
while (lt < rt) {
int res = -2;
if (prv == lt) {
res = Guess(rt);
prv = rt;
}
else if (prv == rt) {
res = -Guess(lt);
prv = lt;
}
else if (dist(gen) == 0) {
Guess(lt);
res = Guess(rt);
prv = rt;
}
else {
Guess(rt);
res = -Guess(lt);
prv = lt;
}
if (res == 0) {
return (lt + rt) / 2;
}
if (res == 1) {
lt = (lt + rt) / 2 + 1;
}
else {
rt = (lt + rt - 1) / 2;
}
}
return lt;
}
int end_game(int dir, int len) {
if (len == 2) {
int res = Guess(fix(dir, 1));
if (res > 0) {
return fix(dir, 1);
}
else {
return fix(dir, 2);
}
}
if (len == 3) {
int res = Guess(fix(dir, 1));
if (res > 0) {
return fix(dir, 1);
}
else if (res < 0) {
return fix(dir, 3);
}
else {
return fix(dir, 2);
}
}
if (len == 4) {
int res = Guess(fix(dir, 2));
if (res > 0) {
res = Guess(fix(dir, 1));
if (res > 0) {
return fix(dir, 1);
}
else {
return fix(dir, 2);
}
}
else if (res < 0) {
return fix(dir, 4);
}
else {
return fix(dir, 3);
}
}
if (len == 5) {
int res = Guess(fix(dir, 3));
if (res > 0) {
res = Guess(fix(dir, 1));
if (res > 0) {
return fix(dir, 1);
}
else if (res < 0) {
return fix(dir, 3);
}
else {
return fix(dir, 2);
}
}
else if (res < 0) {
return fix(dir, 5);
}
else {
return fix(dir, 4);
}
}
if (len == 6) {
int res = Guess(fix(dir, 1));
if (res > 0) {
res = Guess(fix(dir, 3));
if (res > 0) {
return fix(dir, 3);
}
else if (res < 0) {
return fix(dir, 1);
}
else {
return fix(dir, 2);
}
}
else {
res = Guess(fix(dir, 9));
if (res > 0) {
return fix(dir, 6);
}
else if (res < 0) {
return fix(dir, 4);
}
else {
return fix(dir, 5);
}
}
}
if (len == 7) {
int res = Guess(fix(dir, 1));
if (res > 0) {
res = Guess(fix(dir, 3));
if (res > 0) {
return fix(dir, 3);
}
else if (res < 0) {
return fix(dir, 1);
}
else {
return fix(dir, 2);
}
}
else if (res < 0) {
res = Guess(fix(dir, 11));
if (res > 0) {
return fix(dir, 7);
}
else if (res < 0) {
return fix(dir, 5);
}
else {
return fix(dir, 6);
}
}
else {
return fix(dir, 4);
}
}
int k = 3;
while (max_end[k] < len) {
k++;
}
int sum = len + max_end[k - 2] - 2;
int res = Guess(fix(dir, max_end[k - 2] - 2));
if (res < 0) {
return mid_game(fix(dir, sum / 2 + 1), fix(dir, len), fix(dir, max_end[k - 2] - 2));
}
else if (res > 0) {
len = (sum - 1) / 2;
res = Guess(fix(dir, max_end[k - 2]));
if (res < 0) {
return end_game(dir, max_end[k - 2]);
}
else if (res > 0) {
return mid_game(fix(dir, max_end[k - 2]), fix(dir, (sum - 1) / 2), fix(dir, max_end[k - 2]));
}
else {
return fix(dir, max_end[k - 2] - 1);
}
}
else {
return fix(dir, sum / 2);
}
}
int HC(int _N) {
max_end[1] = 3;
max_end[2] = 7;
for (int i = 3; i < 30; i++) {
max_end[i] = max_end[i - 2] + (1 << i);
}
N = _N;
if (N == 1) {
return 1;
}
if (N == 2) {
Guess(1);
int res = Guess(2);
if (res > 0) {
return 2;
}
else {
return 1;
}
}
if (N == 3) {
Guess(1);
int res = Guess(3);
if (res > 0) {
return 3;
}
else if (res < 0) {
return 1;
}
else {
return 2;
}
}
int mid = (N + 2) / 2;
Guess(mid - 2);
int res = Guess(mid);
if (res < 0) {
return end_game(1, mid);
}
else if (res > 0) {
return end_game(-1, N - mid + 1);
}
else {
return mid - 1;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
686 ms |
24364 KB |
Output is partially correct - alpha = 0.206896551724 |
