# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1188814 | racha555 | Aliens (IOI07_aliens) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
define int long long ;
bool ask(int x,int y){
cout<<"examine ";
cout<<x<<" "<<y<<" \n";
string q;
cin>>q;
return q=="true";
}
signed main(){
int n,x,y;
cin>>n>>x>>y;
int raya=1;
while(ask(x+raya,y)){
raya*=2;
if(x+raya>n){
raya=n-x;
break;
}
}
int l,mid,r;
l=x,r=x+raya;
int bestx=x;
while(l<=r){
mid=l+(r-l)/2;
if(ask(mid,y)){
l=mid+1;
bestx=mid;
}
else{
r=mid-1;
}
}
raya=1;
while(ask(bestx-raya,y)){
raya*=2;
if(bestx-raya<1){
raya=bestx;
break;
}
}
l=bestx-raya,r=bestx;
int badx=x;
while(l<=r){
mid=l+(r-l)/2;
if(!ask(mid,y)){
l=mid+1;
badx=mid;
}
else{
r=mid-1;
}
}
badx+=1;
// cout<<badx<<" "<<bestx;
int m=bestx-badx+1;
int midx=bestx-(m/2);
int besty,bady;
l=y;
raya=1;
while(ask(midx,y+raya)){
raya*=2;
if(y+raya>n){
raya=r-y;
}
}
l=y,r=y+raya;
besty=y;
while(l<=r){
mid=l+(r-l)/2;
if(ask(midx,mid)){
l=mid+1;
besty=mid;
}
else{
r=mid-1;
}
}
int midy=besty-m/2;
// cout<<midx<<"--"<<midy;
bool still=true;
while(still){
still=false;
if(ask(midx-m,midy+m)){
still= true;
midx=midx-m;
midy=midy+m;
}
if(!still){
if(ask(midx+m,midy+m)){
still= true;
midx=midx+m;
midy=midy+m;
}
}
if(!still){
if(ask(midx-m,midy)){
still= true;
midx=midx-m;
midy=midy;
}
}
}
cout<<"solution "<<midx+2*m<<" "<<midy-2*m;
}