Submission #163314

#	Time	Username	Problem	Language	Result	Execution time	Memory
163314		Berted	Aliens (IOI07_aliens)	C++14	100 / 100	4 ms	404 KiB

aliens

#include <iostream>
#define int long long
using namespace std;
int n,x,y,lf,rg,sz;
inline bool ask(int x,int y)
{
	if (y<1 || x<1 || x>n || y>n) {return 0;}
	else 
	{
		string rs;
		cout<<"examine "<<x<<" "<<y<<endl;
		cin>>rs;
		return rs=="true";
	}
}
int32_t main()
{	
	cin>>n>>x>>y;
	int l = 1,r = x;
	while (l<r)
	{
		int pv = (l+r)/2;
		if (ask(x-pv,y)) {l = pv+1;}
		else {r = pv;}
	}
	lf = x - (l - 1);
	l = x+1,r = n+1;
	while (l<r)
	{
		int pv = (l+r)/2;
		if (ask(pv,y)) {l = pv+1;}
		else {r = pv;}
	}
	rg = l - 1;
	//cout<<"RANDOM L R BOUND : "<<lf<<" "<<rg<<"\n";
	if (ask(lf - 2*(rg-lf+1),y) || ask(lf + 2*(rg-lf+1),y)) {sz = rg-lf+1;}
	else if ((rg-lf+1)%3==0 && (ask(lf - 2*(rg-lf+1)/3,y) || ask(lf + 2*(rg-lf+1)/3,y))) {sz = (rg-lf+1)/3;}
	else if ((rg-lf+1)%5==0 && (ask(lf - 2*(rg-lf+1)/5,y) || ask(lf + 2*(rg-lf+1)/5,y))) {sz = (rg-lf+1)/5;}
	//cout<<"SIZE FOUND TO BE : "<<sz<<"\n";
	int x1 = lf,y1 = y;
	while (true)
	{
		if (ask(x1 - sz,y1 - sz)) {x1 -= sz; y1 -= sz;}
		else if (ask(x1 - sz,y1 + sz)) {x1 -= sz; y1 += sz;}
		else {break;}
	}
	//cout<<"LOWEST X : "<<x1<<"\n";
	l = 1,r = y;
	while (l<r)
	{
		int pv = (l+r)/2;
		if (ask(x1,y-pv)) {l = pv+1;}
		else {r = pv;}
	}
	y1 = y - (l-1);
	//cout<<"RANDOM TOP Y : "<<y1<<"\n";
	while (true)
	{
		if (ask(x1 - sz,y1 - sz)) {x1 -= sz; y1 -= sz;}
		else if (ask(x1 + sz,y1 - sz)) {x1 += sz; y1 -= sz;}
		else {break;}
	}
	//cout<<"LOWEST Y : "<<y1<<"\n";
	cout<<"solution "<<x1 + 2*sz + sz/2<<" "<<y1 + 2*sz + sz/2<<endl;
	return 0;
}

• 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