Submission #124768

#	Time	Username	Problem	Language	Result	Execution time	Memory
124768		dragonslayerit	Cup of Jamshid (IOI17_cup)	C++14	100 / 100	3 ms	376 KiB

cup

#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);
}

• Subtask 1: 100 / 100