#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
namespace myrand
{
mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
ll Int(ll l,ll r) {return uniform_int_distribution<ll> (l,r)(mt);}
}
using namespace myrand;
const int N = 1e5 + 10;
int HC(int n){
if (n == 1) return 1;
Guess(1);
int g = Guess(n);
int prv = n;
int side, l = 1, r = n; // 0 = left, 1 = right
if (g == 0) return (n + 1) / 2;
if (g == 1) side = 1, l = (n + 1) / 2 + 1;
else side = 0, r = n / 2;
if (side == 0)
while (r - l + 1 > 3)
{
Guess(1);
int mid = r / 4 + 1;
g = Guess(mid * 2 - 1);
if (g == 0) return mid;
if (g == -1) r = mid - 1;
else
{
l = mid + 1;
if (r - l + 1 <= 3) break;
Guess(r);
g = Guess(l);
prv = l;
if (g == 0) return (l + r) / 2;
if (g == -1)
{
l = (l + r) / 2 + 1;
break;
}
else r = (l + r - 1) / 2;
g = Guess(r);
prv = r;
if (g == 0) return (l + r) / 2;
if (g == 1) l = (l + r) / 2 + 1;
else r = (l + r - 1) / 2;
break;
}
}
else
while (r - l + 1 > 3)
{
Guess(n);
int mid = n - (n - l + 1) / 4;
g = Guess(mid * 2 - n);
if (g == 0) return mid;
if (g == -1) l = mid + 1;
else
{
r = mid - 1;
if (r - l + 1 <= 3) break;
Guess(l);
g = Guess(r);
prv = r;
if (g == 0) return (l + r) / 2;
if (g == 1) l = (l + r) / 2 + 1;
else
{
r = (l + r - 1) / 2;
break;
}
g = Guess(l);
prv = l;
if (g == 0) return (l + r) / 2;
if (g == -1) l = (l + r) / 2 + 1;
else r = (l + r - 1) / 2;
break;
}
}
if (l == r) return l;
if (r - l + 1 <= 3)
{
Guess(l);
g = Guess(r);
if (g == 0) return (l + r) / 2;
if (g == 1) return r;
return l;
}
Guess(l);
prv = l;
while (l < r)
{
int flag_r = 0, flag_l = 0;
if (r - l > 1 && (r - l) & 1)
{
if (l != prv) flag_r = 1, r--;
else flag_l = 1, l++;
}
int mid = (l + r) / 2;
if (prv <= l)
{
g = Guess(r + l - prv);
prv = r + l - prv;
if (g == 0) return mid;
if (g == -1)
{
r = mid - 1;
l -= flag_l;
}
else
{
l = mid + 1;
r += flag_r;
}
}
else
{
g = Guess(l - (prv - r));
prv = l - (prv - r);
if (g == 0) return mid;
if (g == -1)
{
l = mid + 1;
r += flag_r;
}
else
{
r = mid - 1;
l -= flag_l;
}
}
}
return l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
729 ms |
10076 KB |
Output is partially correct - alpha = 0.400000000000 |
