// M
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
int n;
int SolveType2(int l, int r)
{
assert(l - 1 >= r - l + 1);
assert(n - r >= r - l + 1);
int last = l;
Guess(l);
while (l < r)
{
int tobe = -1;
if (last <= l)
tobe = r + (l - last);
else if (last >= r)
tobe = l - (last - r);
else
assert(0);
assert(tobe >= 1 && tobe <= n);
int w = Guess(tobe);
if (w == 0)
return (last + tobe) / 2;
if (l + 1 == r)
{
if ((w == 1 && tobe > last) || (w == -1 && tobe < last))
return r;
return l;
}
if ((w == 1 && tobe > last) || (w == -1 && tobe < last))
l = (l + r) / 2 + 1;
else
r = (l + r - 1) / 2;
last = tobe;
}
assert(l == r);
return l;
}
int SolveType1(int l, int r, int asked = 0)
{
if (r - l == 0)
return l;
if (!asked)
Guess(l);
if (r - l == 1)
{
int w = Guess(r);
if (w == 1)
return r;
return l;
}
if (r - l == 2)
{
int w = Guess(r);
if (w == 1)
return r;
if (w == 0)
return r - 1;
return l;
}
int md = (r - l + 1) / 3 * 2 + l - 1;
int w = Guess(md);
if (w == 0)
return (l + md) / 2;
if (w == -1)
return SolveType1(l, (l + md - 1) / 2);
assert(md + 2 <= r);
w = Guess(md + 2);
if (w == 0)
return md + 1;
if (w == 1)
return SolveType1(md + 2, r, 1);
return SolveType2((l + md) / 2 + 1, md);
}
int HC(int _n)
{
n = _n;
return SolveType1(1, n);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
778 ms |
24544 KB |
Output is partially correct - alpha = 0.600000000000 |
