| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1051669 | Dennis_Jason | Aliens (IOI07_aliens) | C++14 | 0 ms | 0 KiB |
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 NMAX 200001
#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF 1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
*
*
----------------DEMONSTRATION-------------------
Steps:
1.Find Xright in given red cell
=>M=xr-xl
2.find Xleft in given red cell
3.Find Ydown in given red cell => Yup=Ydown+m
4.find cell_up,cell_right,cell_down,cell_left
5.print Xc,Yc :)
BIG FAIL :((((
---------------------END------------------------
*/
/*-------------Initialize------------*/
int n,x,y;
int Xr,Xl,Yu,Yd,Xc,Yc;
int Wl,Wr,Wd;
int m;
int Cl,Cr,Cd,Cu;
int mid_x,mid_y;
void find_Wl()
{
int red=1;
int cur=x;
int k=0;
while(red==1)
{
cur=x-(1LL << k);
if(cur<0)
cur=0;
Wl=cur;
k++;
cout.flush()<<"examine "<<cur<<" "<<y<<nl;
cout.flush();
string word;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red==0)
break;
}
Wl=max(0,Wl);
}
void find_Wr()
{
int red=1;
int cur=x;
int k=0;
while(red==1)
{
cur=x+(1LL << k);
if(cur>n)
cur=n;
Wr=cur;
k++;
cout.flush()<<"examine "<<cur<<" "<<y<<nl;
cout.flush();
string word;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red==0)
break;
}
Wr=min(n,Wr);
}
void find_Xl()
{
int st=Wl;
int dr=Wr;
while(st<=dr)
{
int mid=(st+dr)/2;
cout.flush()<<"examine "<<mid<<" "<<y<<nl;
cout.flush();
string word;
cin>>word;
int red;
if(word=="false")
red=0;
else
red=1;
if(red)
{
dr=mid-1;
Xl=mid;
}
else
st=mid+1;
}
}
void find_Xr()
{
int st=Wl;
int dr=Wr;
while(st<=dr)
{
int mid=(st+dr)/2;
cout.flush()<<"examine "<<mid<<" "<<y<<nl;
cout.flush();
string word;
int red;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red)
{
st=mid+1;
Xr=mid;
}
else
dr=mid-1;
}
}
void calc_m()
{
m=(Xr-Xl+1);
}
void find_cell_mid()
{
int up=0,down=0;
//up
int st=y;
int dr=y+m+1;
while(st<=dr)
{
int mid=(st+dr)/2;
cout.flush()<<"examine "<<x<<" "<<mid<<nl;
cout.flush();
string word;
int red;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red)
{
up=mid;
st=mid+1;
}
else
dr=mid-1;
}
// down
st=y-(m+1);
dr=y;
while(st<=dr)
{
int mid=(st+dr)/2;
cout.flush()<<"examine "<<x<<" "<<mid<<nl;
cout.flush();
string word;
int red;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red)
{
down=mid;
dr=mid-1;
}
else
st=mid+1;
}
mid_x=(Xl+Xr)/2;
mid_y=(up+down)/2;
}
void left_up()
{
int red=1;
int cur_x=mid_x;
int cur_y=mid_y;
while(red)
{
cur_x-=m;
cur_y+=m;
cout.flush()<<"examine "<<cur_x<<" "<<cur_y<<nl;
cout.flush();
string word;
red;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red==0)
break;
mid_x=cur_x;
mid_y=cur_y;
}
}
void left()
{
int red=1;
int cur=mid_x;
while(red)
{
cur-=2*m;
cout.flush()<<"examine "<<cur<<" "<<mid_y<<nl;
cout.flush();
string word;
int red;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red==0)
break;
mid_x=cur;
}
}
void up()
{
int red=1;
int cur=mid_y;
while(red)
{
cur+=2*m;
cout.flush()<<"examine "<<mid_x<<" "<<cur<<nl;
cout.flush();
string word;
int red;
cin>>word;
if(word=="false")
red=0;
else
red=1;
if(red==0)
break;
mid_y=cur;
}
}
void find_solution()
{
Xc=mid_x+2*m;
Yc=mid_y-2*m;
}
void print_solution()
{
cout.flush()<<"solution "<<Xc<<" "<<Yc<<nl;
cout.flush();
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>x>>y;
find_Wl();
find_Wr();
find_Xl();
find_Xr();
calc_m();
find_cell_mid();
left_up();
left();
up();
find_solution();
print_solution();
return 0;
}