#include "cup.h"
#include <cassert>
#include <cstdio>
int dx[4]={1,0,0,1};
int dy[4]={0,0,1,1};
//know cup is in [x,x+2^k)x[y,y+2^k)
std::vector<int> solve(int x,int y,int k){
//fprintf(stderr,"solve(%d,%d,2^%d)\n",x,y,k);
if(k==0) return {x,y};
//fprintf(stderr,"asking (%d,%d)\n",x,y-(1<<(k-1)));
int res=(long long)ask_shahrasb(x,y-(1<<(k-1)))>>(k-1);
assert(res>=0&&res<4);
//fprintf(stderr,"res=%d\n",res);
return solve(x+(dx[res]<<(k-1)),y+(dy[res]<<(k-1)),k-1);
}
std::vector<int> find_cup() {
int x=(ask_shahrasb(-(1<<29),0)>>29)?0:-5e8;
int y=(ask_shahrasb(0,-(1<<29))>>29)?0:-5e8;
return solve(x,y,29);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
