Submission #890384

#	Time	Username	Problem	Language	Result	Execution time	Memory
890384		Faisal_Saqib	Aliens (IOI07_aliens)	C++17	40 / 100	2 ms	440 KiB

aliens

#include <iostream>
using namespace std;
#define int long long
const int M=300; // Trying for 100 points
// const int M=102; // Trying for 40/60 points
int n,m=-1;
int factor_y=1;
int factor_x=1;
string ans;
pair<int,int> just_do_it(int x0,int y0,bool swp=0) // One call take atmost M queries
{
	if(m!=-1)
	{
		// We can do a binary_search
		//O(lg m)
		// m + 6* lg m
		int s=0;
		int e=m+1;
		int to_right=0;
		if(!swp)
		{
			while(s+1<e)
			{
				int mid=(s+e)/2;
				if(((x0+(mid*factor_x))>n))
				{
					e=mid;
				}
				else
				{
					cout<<"examine "<<x0+(mid*factor_x)<<' '<<y0<<endl;
					cin>>ans;
					if(ans=="false")
					{
						e=mid;
					}
					else
					{
						s=mid;
					}
				}
			}
			to_right=s;
			s=0;
			e=m+1;
			while(s+1<e)
			{
				int mid=(s+e)/2;
				if(((x0-(mid*factor_x))<1))
				{
					e=mid;
				}
				else
				{
					cout<<"examine "<<x0-(mid*factor_x)<<' '<<y0<<endl;
					cin>>ans;
					if(ans=="false")
					{
						e=mid;
					}
					else
					{
						s=mid;
					}
				}
			}
			return {to_right,s};
		}
		else
		{
			while(s+1<e)
			{
				int mid=(s+e)/2;
				if(((y0+(mid*factor_y))>n))
				{
					e=mid;
				}
				else
				{
					cout<<"examine "<<x0<<' '<<y0+(mid*factor_y)<<endl;
					cin>>ans;
					if(ans=="false")
					{
						e=mid;
					}
					else
					{
						s=mid;
					}
				}
			}
			to_right=s;
			s=0;
			e=m+1;
			while(s+1<e)
			{
				int mid=(s+e)/2;
				if(((y0-(mid*factor_y))<1))
				{
					e=mid;
				}
				else
				{
					cout<<"examine "<<x0<<' '<<y0-(mid*factor_y)<<endl;
					cin>>ans;
					if(ans=="false")
					{
						e=mid;
					}
					else
					{
						s=mid;
					}
				}
			}
			return {to_right,s};
		}
	}
	int to_right=-1;
	for(int j=1;j<=M;j++)
	{
		if(swp and (y0+(j*factor_y))>n)
		{
			to_right=j-1;
			break;
		}
		if(!swp and (x0+(j*factor_x))>n)
		{
			to_right=j-1;
			break;
		}
		if(swp)
		{
			cout<<"examine "<<x0<<' '<<y0+(j*factor_y)<<endl;
		}
		else
		{
			cout<<"examine "<<x0+(j*factor_x)<<' '<<y0<<endl;
		}
		cin>>ans;
		if(ans=="false")
		{
			to_right=j-1;
			break;
		}
	}
	if(to_right==-1)
		to_right=M;
	// if(m!=-1)
	// {
	// 	return {to_right,m-to_right-1};
	// }
	int to_left=-1;
	for(int j=1;j<=M;j++)
	{
		if(swp and (y0-(j*factor_y))<1)
		{
			to_left=j-1;
			break;
		}
		if(!swp and (x0-(j*factor_x))<1)
		{
			to_left=j-1;
			break;
		}
		if(swp)
		{
			cout<<"examine "<<x0<<' '<<y0-(j*factor_y)<<endl;
		}
		else
		{
			cout<<"examine "<<x0-(j*factor_x)<<' '<<y0<<endl;
		}
		cin>>ans;
		if(ans=="false")
		{
			to_left=j-1;
			break;
		}
	}
	if(to_left==-1)
		to_left=M;
	return {to_right,to_left};
}
signed main()
{
	int x0,y0;
	cin>>n>>x0>>y0;
	auto ap=just_do_it(x0,y0);
	int to_right=ap.first;
	int to_left=ap.second;
	m=to_left+to_right+1;
	// cout<<m<<endl;
	ap=just_do_it(x0,y0,1);
	int to_up=ap.first;
	int to_down=ap.second;
	// cout<<to_left<<' '<<to_right<<endl;
	// cout<<to_up<<' '<<to_down<<endl;
	int right_most = x0+to_right;
	int left_most  = x0-to_left;
	int up_most = y0+to_up;
	int down_most  = y0-to_down;
	int center_x = (right_most+left_most)/2;
	int center_y = (up_most+down_most)/2;
	// cout<<center_y<<' '<<center_x<<endl;
	int final_x,final_y;
	factor_x=(2*m);
	factor_y=(2*m);
	ap=just_do_it(center_x,center_y);
	int block_right=ap.first;
	int block_left=ap.second;
	final_x = ((center_x - 2ll*block_left*m) + (center_x + 2ll*block_right*m))/2;
	ap=just_do_it(center_x,center_y,1);
	int block_up=ap.first;
	int block_down=ap.second;
	final_y = ((center_y - 2ll*block_down*m) + (center_y + 2ll*block_up*m))/2;
	cout<<"solution "<<final_x<<' '<<final_y<<endl;
	return 0;
}

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