제출 #411232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411232		Jasiekstrz	Aliens (IOI07_aliens)	C++17	100 / 100	4 ms	212 KiB

aliens

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
bool okk(int x,int y,int n)
{
	return (0<x && x<=n && 0<y && y<=n);
}
bool ask(int x,int y)
{
	cout<<"examine "<<x<<" "<<y<<endl;
	string input;
	cin>>input;
	return (input=="true");
}
int find_right(int n,int x,int y)
{
	int bg=0,en=(n-x)/4;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		bool ok=true;
		for(int i:{1,2,4})
		{
			if(!ask(x+i*mid,y))
			{
				ok=false;
				break;
			}
		}
		if(ok)
			bg=mid;
		else
			en=mid-1;
	}
	bg*=4;
	while(x+bg+1<=n)
	{
		if(!ask(x+bg+1,y))
			break;
		bg++;
	}
	return bg;
}
int find_left(int n,int x,int y)
{
	int bg=0,en=(x-1)/4;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		bool ok=true;
		for(int i:{1,2,4})
		{
			if(!ask(x-i*mid,y))
			{
				ok=false;
				break;
			}
		}
		if(ok)
			bg=mid;
		else
			en=mid-1;
	}
	bg*=4;
	while(x-bg-1>=1)
	{
		if(!ask(x-bg-1,y))
			break;
		bg++;
	}
	return bg;
}
int find_up(int n,int x,int y)
{
	int bg=0,en=(n-y)/4;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		bool ok=true;
		for(int i:{1,2,4})
		{
			if(!ask(x,y+i*mid))
			{
				ok=false;
				break;
			}
		}
		if(ok)
			bg=mid;
		else
			en=mid-1;
	}
	bg*=4;
	while(y+bg+1<=n)
	{
		if(!ask(x,y+bg+1))
			break;
		bg++;
	}
	return bg;
}
int main()
{
	int n,x,y;
	cin>>n>>x>>y;
	int r=find_right(n,x,y);
	int l=find_left(n,x,y);
	int u=find_up(n,x,y);
	int m=l+r+1;
	x=x-l+(m/2);
	y=y+u-(m/2);
	//cerr<<r<<" "<<l<<" "<<u<<" "<<m<<" "<<x<<" "<<y<<endl;
	int a,b;
	for(a=1;okk(x-a*m,y-a*m,n) && ask(x-a*m,y-a*m);a++);
	for(b=1;okk(x+b*m,y+b*m,n) && ask(x+b*m,y+b*m);b++);
	x+=m*(b-a)/2;
	y+=m*(b-a)/2;
	for(a=1;okk(x-a*m,y+a*m,n) && ask(x-a*m,y+a*m);a++);
	for(b=1;okk(x+b*m,y-b*m,n) && ask(x+b*m,y-b*m);b++);
	x+=m*(b-a)/2;
	y-=m*(b-a)/2;
	cout<<"solution "<<x<<" "<<y<<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