#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) {
return lt;
}
if (lt > rt) {
swap(lt, rt);
}
int len = 1;
while (len < rt - lt + 1) {
len = len * 2 + 1;
}
int mt = -1;
if (prv < rt - len + 1) {
mt = rt - len / 2;
}
else if (prv > lt + len - 1) {
mt = lt + len / 2;
}
else if (prv <= lt) {
mt = prv + len / 2;
}
else {
mt = prv - len / 2;
}
int nxt = mt * 2 - prv;
int res = Guess(nxt);
if (res == 0) {
return mt;
}
else if ((prv < nxt && res < 0) || (prv > nxt && res > 0)) {
return mid_game(lt, mt - 1, nxt);
}
else {
return mid_game(mt + 1, rt, nxt);
}
}
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 |
22 ms |
1304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
629 ms |
8108 KB |
Output is partially correct - alpha = 1.000000000000 |
