This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
ll n,x,y,xmx,xmn,ymx,ymn,len,xl,xr,yr,l,r,M;
struct Interactive
{
int a[105][105],n,m,x0,y0,i,j;
void Init(int _n,int _m,int _x0,int _y0)
{
n=_n; m=_m; x0=_x0; y0=_y0;
for(i=x0;i<=x0+5*m-1;i++)
for(j=y0;j<=y0+5*m-1;j++)
{
int x=i-x0,y=j-y0;
if((x/m+y/m)%2==0) a[i][j]=1;
}
}
void debug()
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) cout<<a[i][j]<<" ";
cout<<'\n';
}
}
} IR;
int ask(int x,int y)
{
cout<<"examine "<<x<<" "<<y<<'\n';
// return IR.a[x][y];
string s;
cin>>s;
return (s=="true");
}
int main()
{
// freopen("aliens.inp","r",stdin);
//freopen("aliens.out","w",stdout);
ll x0,y0;
cin>>n>>x0>>y0;
// IR.Init(19,3,5,2);
//IR.debug();
for(len=1;len<=30;len++)
{
ll x=x0+(1<<len)-1;
if(x>n || ask(x,y0)==0) break;
}
len--;
x=x0+(1<<len)-1;
l=x,r=min(n,x+(1<<len));
while(l<r)
{
ll mid=(l+r+1)>>1;
if(ask(mid,y0)) l=mid; else r=mid-1;
}
xr=l;
for(len=1;len<=30;len++)
{
ll x=x0-(1<<len)+1;
if(x<1 || ask(x,y0)==0) break;
}
len--;
x=x0-(1<<len)+1;
l=max(1LL,x-(1<<len)),r=x;
while(l<r)
{
ll mid=(l+r)>>1;
if(ask(mid,y0)) r=mid; else l=mid+1;
}
xl=l;
M=xr-xl+1;
for(len=1;len<=30;len++)
{
ll y=y0+(1<<len)-1;
if(y>n || ask(x0,y)==0) break;
}
len--;
y=y0+(1<<len)-1;
l=y,r=min(n,y+(1<<len));
while(l<r)
{
ll mid=(l+r+1)>>1;
if(ask(x0,mid)) l=mid; else r=mid-1;
}
yr=l;
for(xmn=xr;xmn>=1;xmn-=2*M)
if(ask(xmn,yr)==0) break;
xmn=xmn+2*M-M+1;
for(xmx=xr;xmx<=n;xmx+=2*M)
if(ask(xmx,yr)==0) break;
xmx=xmx-2*M;
for(ymn=yr;ymn>=1;ymn-=2*M)
if(ask(xr,ymn)==0) break;
ymn=ymn+2*M-M+1;
for(ymx=yr;ymx<=n;ymx+=2*M)
if(ask(xr,ymx)==0) break;
ymx=ymx-2*M;
cout<<"solution "<<(xmn+xmx)/2<<" "<<(ymn+ymx)/2;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |