| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1260883 | jump | Aliens (IOI07_aliens) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
int lim=10000000,x,y;
int u,d,l,r;
int USE = 0;
int CENTERx,CENTERy,SIMM;
bool examine(int X,int Y);
void getrxy(){
bool found = false;
int rx;
int ry;
while(!found){
rx = CENTERx-SIMM*5+rand()%(SIMM*10);
ry = CENTERy-SIMM*5+rand()%(SIMM*10);
if(examine(rx,ry)){
x=rx;
y=ry;
found = true;
}
std::cout << rx << ' ' << ry << '\n';
}
}
bool examine(int X,int Y){
int x0 = CENTERx - SIMM - SIMM - SIMM/2;
int y0 = CENTERy - SIMM - SIMM - SIMM/2;
int dx = X - x0;
int dy = Y - y0;
if (dx < 0 || dy < 0 || dx >= 5*SIMM || dy >= 5*SIMM)
return 0;
else
{
dx = dx / SIMM;
dy = dy / SIMM;
if ((dx+dy) % 2 == 0)
return 1;
else
return 0;
}
}
bool test(int tx,int ty){
USE++;
if(tx>lim||ty>lim||tx<=0||ty<=0)return false;
//return examine(tx,ty);
std::cout << "examine " << tx << ' ' << ty << std::endl;
std::flush();
std::string in;
std::cin >> in;
return in[0]=='t';
}
void ans(int tx,int ty){
//return solution(tx,ty);
std::cout << "solution " << tx << ' ' << ty << std::endl;
std::flush();
}
bool up(int x,int y,int t){return test(x,y+t);}
bool down(int x,int y,int t){return test(x,y-t);}
bool left(int x,int y,int t){return test(x-t,y);}
bool right(int x,int y,int t){return test(x+t,y);}
int find(std::function<bool(int,int,int)> f){
bool first = true;
int l=1,h=-1;
int last=l;
while(h==-1){
if(f(x,y,l)){
first = false;
last=l;
l*=2;
}
else{
if(first)return 0;
h = l;
}
}
l=last;h-=1;
while(l<h){
int mid = (l+h+1)/2;
if(f(x,y,mid)){
l = mid;
}
else{
h = mid-1;
}
}
return l;
}
void fans(int cmx,int cmy,int m){
int tr=2;
int xd=1;
int yd=1;
if(test(cmx+2*m,cmy))xd+=1;
if(test(cmx+2*2*m,cmy))xd+=1;
if(test(cmx,cmy+2*m))yd+=1;
if(test(cmx,cmy+2*2*m))yd+=1;
if((xd==1&&yd==2)||(xd==1&&yd==1)||(xd==2&&yd==1)){
if(test(cmx+m,cmy+m)){
int ax,ay;
if(xd==1)ax = cmx-m;
else ax = cmx+m;
if(yd==1)ay = cmy-m;
else ay = cmy + m;
ans(ax,ay);
}
else{
ans(cmx-(2-xd)*2*m,cmy-(2-yd)*2*m);
}
}
else if(xd==2&&yd==2){
if(test(cmx-2*m,cmy-2*m)){
ans(cmx,cmy);
}
else{
ans(cmx+m,cmy+m);
}
}
else{
ans(cmx-(2-xd)*2*m,cmy-(2-yd)*2*m);
}
}
signed main() {
//srand(time(nullptr));
SIMM=3+rand();
CENTERx=SIMM*3+rand();CENTERy=SIMM*3+rand();
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
//std::cin >> lim >> x >> y;
getrxy();
int u = find(up);
int l = find(left);
int r = find(right);
int d = find(down);
int m = (1+l+r);
int cmx = x-l+m/2;
int cmy = y-d+m/2;
//std::cout << u << ' ' << l << ' ' << r << ' ' << d << ' ' << m << ' ' << cmx << ' ' << cmy;
fans(cmx,cmy,m);
return 0;
}