#include <bits/stdc++.h>
#include "grader.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
int n;
int solve(int a, int b, int last)
{
if(b-a+1 == 4)
{
Guess(a);
int res = Guess(a+2);
if(res == 0)
{
return a+1;
}
else if(res == -1)
{
return a;
}
else
{
int foo = Guess(a+3);
if(foo == 1) return a+3;
return a+2;
}
}
if(b-a+1 == 3)
{
Guess(a);
int res = Guess(a+2);
if(res == 0) return a+1;
if(res == 1) return a+2;
return a;
}
if(b-a+1 == 2)
{
Guess(a);
int res = Guess(a+1);
if(res == 1) return a+1;
return a;
}
if(a == b) return a;
if(last == a)
{
int res = Guess(b);
int mid = (a+b)/2;
if((a+b)%2 == 1)
{
assert(res);
if(res == 1) return solve(mid+1, b, b);
return solve(a, mid, b);
}
else
{
if(res == 0) return mid;
if(res == 1) return solve(mid+1, b, b);
return solve(a, mid-1, b);
}
}
else if(last == b)
{
int res = Guess(a);
int mid = (a+b)/2;
if((a+b)%2 == 1)
{
assert(res);
if(res == 1) return solve(a, mid, a);
return solve(mid+1, b, a);
}
else
{
if(res == 0) return mid;
if(res == 1) return solve(a, mid-1, a);
return solve(mid+1, b, a);
}
}
else
{
int mid = (a+b)/2;
if(last> b)
{
int dx = last-b;
if(1<= a-dx)
{
int res = Guess(a-dx);
if((a+b)%2 == 1)
{
assert(res);
if(res == 1) return solve(a, mid, a-dx);
return solve(mid+1, b, a-dx);
}
else
{
if(res == 0) return mid;
if(res == 1) return solve(a, mid-1, a-dx);
return solve(mid+1, b, a-dx);
}
}
}
else if(last< a)
{
int dx = a-last;
if(b+dx<= n)
{
int res = Guess(b+dx);
if((a+b)%2 == 1)
{
assert(res);
if(res == 1) return solve(mid+1, b, b+dx);
return solve(a, mid, b+dx);
}
else
{
if(res == 0) return mid;
if(res == 1) return solve(mid+1, b, b+dx);
return solve(a, mid-1, b+dx);
}
}
}
Guess(a);
int res = Guess(b);
if((a+b)%2 == 1)
{
assert(res);
if(res == 1) return solve(mid+1, b, b);
return solve(a, mid, b);
}
else
{
if(res == 0) return mid;
if(res == 1) return solve(mid+1, b, b);
return solve(a, mid-1, b);
}
}
}
int HC(int N)
{
n = N;
return solve(1, N, -1);
}
Compilation message
hottercolder.cpp: In function 'int HC(int)':
hottercolder.cpp:111:4: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
if(b+dx<= n)
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
830 ms |
8312 KB |
Output is partially correct - alpha = 0.222222222222 |
