Submission #168999

#	Time	Username	Problem	Language	Result	Execution time	Memory
168999		Lawliet	Aliens (IOI07_aliens)	C++14	100 / 100	4 ms	376 KiB

aliens

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;

int n;

bool check(lli X, lli Y)
{
	if( X > n || Y > n ) return false;
	if( X <= 0 || Y <= 0 ) return false;

	cout << "examine " << X << " " << Y << endl;

	string s;
	cin >> s;

	return s[0] == 't';
}

pii bs(pii p, int dx, int dy)
{
	lli L = 0;
	lli R = n;

	lli X = p.first;
	lli Y = p.second;

	while( R - L > 1 )
	{
		lli m = ( L + R )/2;

		if( check( X + m*dx , Y + m*dy ) ) L = m;
		else R = m;
	}

	return { X + L*dx , Y + L*dy };
}

pii middleDiagonal(pii p, int dx, int dy)
{
	pii E1 = bs( p , dx , dy );
	pii E2 = bs( p , -dx , -dy );

	lli X = E1.first + E2.first;
	lli Y = E1.second + E2.second;

	return { X/2 , Y/2 };
}

int main()
{
	int X, Y;
	cin >> n >> X >> Y;

	pii curPoint = { X , Y };

	curPoint = bs( curPoint , -1 , 0 );
	curPoint = bs( curPoint , 0 , -1 );

	curPoint = middleDiagonal( curPoint , 1 , 1 );
	curPoint = middleDiagonal( curPoint , 1 , -1 );

	cout << "solution " << curPoint.first << " " << curPoint.second << endl;
}

• 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