#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) ((int)v.size())
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forbe(i,b,e) for(int i = b; i < e; ++i)
#define pb push_back
#define pry puts("YES")
#define prn puts("NO")
#define endl '\n'
#define fst first
#define scn second
#define query(x) if(last != x) { val=ask(x); if(val==0&&last!=-1) return (x+last)>>1; last=x; }
int Guess(int x);
int n;
int LAST;
int R;
int cnt;
#ifdef ONPC
int
Guess(int x)
{
++cnt;
#ifdef ONPC
#ifndef ONTST
cout << "Question: " << x << endl;
#endif
#endif
if (LAST == -1) {
LAST = x;
return 0;
}
if (abs(LAST-R) > abs(x-R)) {
LAST = x;
return 1;
}
if (abs(LAST-R) < abs(x-R)) {
LAST = x;
return -1;
}
LAST = x;
return 0;
}
#endif
int
ask(int x)
{
assert(x>0);
assert(x<=n);
return Guess(x);
}
int
specialcase(int last, int l, int r)
{
#ifdef ONPC
#ifndef ONTST
cout << "Special Case " << l << ' ' << r << endl;
#endif
#endif
int val = 0;
if (r == l) return l;
if (r - l == 1) {
query(r);
query(l);
if (val == 1) return l;
else return r;
}
if (r - l == 2) {
query(r);
query(l);
if (val == 0) return l+1;
else if (val==1) return l;
else return r;
}
if (r - l == 3) {
query(r-1);
query(l+1);
if (val == 1) {
query(l);
if (val == 1) return l;
else return l+1;
} else {
query(r);
if (val == 1) return r;
else return r-1;
}
}
if (r - l == 4) {
query(r-1);
query(l+1);
if (val == 1) {
query(l);
if (val == 1) return l;
else return l+1;
} else {
query(r);
query(r-1);
if (val == 1) return r-1;
else return r;
}
}
if (r - l == 5) {
query(r-2);
query(l+2);
if (val == 1) {
query(l);
if (val == 1) return l;
else return l+2;
} else {
query(r);
if (val == 1) {
query(r-1);
if (val == 1) return r-1;
else return r;
} else {
return (r-2);
}
}
}
return 0;
}
int
HC(int _n)
{
n = _n;
int r, l;
int val, last = -1;
int tr,tl;
l = 1;
r = _n;
if (r - l < 2) return specialcase(last, l,r);
int mid = (r+l+1)>>1;
tl = mid;
tr = mid+1;
query(tl);
query(tr);
if (val == 1)
l = (tl+tr+2)>>1;
else
r = (tl+tr-1)>>1;
while (l < r) {
/* if (r - l < 2) return specialcase(last, l,r); */
mid = (r+l+1)>>1;
/* cout << last << ' ' << r << ' ' << l << ' ' << mid << endl; */
tl = last;
if (tl >= r) {
tr = l + (r-last);
tr = max(tr,1);
query(tr);
if (val==1)
r = (tl+tr-1)>>1;
else
l = (tl+tr+2)>>1;
} else {
tr = r + (l-last);
tr = min(tr,n);
query(tr);
if (val==1)
l = (tl+tr+2)>>1;
else
r = (tl+tr-1)>>1;
}
}
return l;
}
#ifdef ONPC
int
check(int x, int r)
{
cnt = 0;
LAST = -1;
R = r;
/* cout << HC(x) << endl; */
return HC(x);
}
void
solve()
{
int _n, _y;
cin >> _n;
cin >> _y;
int mval = _n * 3;
mval = 31-__builtin_clz(mval);
int val = check(_n,_y);
cout << _n << ' ' << val << endl;
#ifndef ONTST
cout << "VALS: " << _n << ' ' << _y << ' ' << mval << endl;
cout << "ANS: " << val << ' ' << cnt << endl;
#endif
}
int32_t
main()
{
#ifndef ONTST
freopen("in", "r", stdin);
#endif
int t = 1;
while(t--)
solve();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
1300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
575 ms |
8100 KB |
Output is partially correct - alpha = 0.208333333333 |
