Submission #120367

#	Time	Username	Problem	Language	Result	Execution time	Memory
120367		baluteshih	Aliens (IOI07_aliens)	C++14	100 / 100	4 ms	412 KiB

aliens

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll n;

ll query(ll x,ll y)
{
	if(x<=0||y<=0||x>n||y>n) return 0;
	cout << "examine " << x << " " << y << endl;
	string s;
	cin >> s;
	return (s[0]=='t');
}
 
int main()
{
	ll x,y,L,R,l,r,dis,m;
	cin >> n >> x >> y;
	l=x,r=n+1;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(query(mid,y)==1) l=mid+1;
		else r=mid;
	}
	R=l,l=0,r=x;
	while(l<r)
	{
		ll mid=(l+r)/2+1;
		if(query(mid,y)==0) l=mid;
		else r=mid-1;
	}
	L=l,dis=R-L-1;
	//cout << "part2: " << L << " " << R << endl;
	ll c=L+R>>1,cx,cy;
	if(query(c,y)==0) m=dis/3;
	else if(dis%5==0)
		if(query(c+dis/5,y)==0) m=dis/5;
		else m=dis;
	else m=dis;
	//cout << "part3: " << m << endl;
	l=x,r=x+m;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(query(mid,y)==1) l=mid+1;
		else r=mid;
	}
	R=l,l=x-m,r=x;
	while(l<r)
	{
		ll mid=(l+r)/2+1;
		if(query(mid,y)==0) l=mid;
		else r=mid-1;
	}
	L=l,cx=L+R>>1;
	//cout << "part4: " << cx << endl;
	l=y,r=y+m;
	while(l<r)
	{
		ll mid=l+r>>1;
		if(query(cx,mid)==1) l=mid+1;
		else r=mid;
	}
	R=l,l=y-m,r=y;
	while(l<r)
	{
		ll mid=(l+r)/2+1;
		if(query(cx,mid)==0) l=mid;
		else r=mid-1;
	}
	L=l,cy=L+R>>1;
	//cout << "part5: " << cy << endl;
	l=query(cx,cy+2*m)+query(cx,cy+4*m);
	r=query(cx,cy-2*m)+query(cx,cy-4*m);
	if(l+r==2)
		if(l==2) cy+=2*m;
		else if(r==2) cy-=2*m;
		else;
	else
		if(l==1) cy+=m,cx+=m;
		else cy-=m,cx+=m;
	
	c=query(cx+2*m,cy)+query(cx+4*m,cy);
	if(c==2) cx+=2*m;
	else if(c==0) cx-=2*m;
	
	cout << "solution " << cx << " " << cy << endl;
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:34:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
aliens.cpp:47:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll c=L+R>>1,cx,cy;
       ~^~
aliens.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
aliens.cpp:68:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  L=l,cx=L+R>>1;
         ~^~
aliens.cpp:73:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
aliens.cpp:84:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  L=l,cy=L+R>>1;
         ~^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10