oj.uz

Submission #411232

# Submission time Handle Problem Language Result Execution time Memory
411232 2021-05-24T18:24:44 Z Jasiekstrz Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 212 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 3 ms 200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 3 ms 200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 4 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 4 ms 200 KB Output is correct