제출 #769492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769492		eliasol	Aliens (IOI07_aliens)	C++14	80 / 100	2 ms	288 KiB

aliens

#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>

bool examine(int x, int y)
{
	std::cout << "examine " << x << " " << y << std::endl;
	std::string res;
	std::cin >> res;
	return res == "true";
}

void solution(int x, int y)
{
	std::cout << "solution " << x << " " << y << std::endl;
}

int main()
{
	int N, X0, Y0;
	std::cin >> N >> X0 >> Y0;

	int l = 1, r = N - X0 + 1;
	int countl, countr, countu, countd;
	while (l < N - X0 + 1)
	{
		int ask = std::min(2 * l, N - X0 + 1);
		if (examine(X0 + ask - 1, Y0))
			l = ask;
		else
		{
			r = ask - 1;
			break;
		}
	}

	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (examine(X0 + m - 1, Y0))
			l = m;
		else
			r = m - 1;
	}

	countr = l - 1;

	l = 1, r = X0;
	while (l < X0)
	{
		int ask = std::min(2 * l, X0);
		if (examine(X0 - ask + 1, Y0))
			l = ask;
		else
		{
			r = ask - 1;
			break;
		}
	}

	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (examine(X0 - m + 1, Y0))
			l = m;
		else
			r = m - 1;
	}

	countl = l - 1;

	l = 1, r = N - Y0 + 1;
	while (l < N - Y0 + 1)
	{
		int ask = std::min(2 * l, N - Y0 + 1);
		if (examine(X0, Y0 + ask - 1))
			l = ask;
		else
		{
			r = ask - 1;
			break;
		}
	}

	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (examine(X0, Y0 + m - 1))
			l = m;
		else
			r = m - 1;
	}

	countu = l - 1;

	l = 1, r = Y0;
	while (l < Y0)
	{
		int ask = std::min(2 * l, Y0);
		if (examine(X0, Y0 - ask + 1))
			l = ask;
		else
		{
			r = ask - 1;
			break;
		}
	}

	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (examine(X0, Y0 - m + 1))
			l = m;
		else
			r = m - 1;
	}

	countd = l - 1;

	assert(countl + countr == countd + countu);

	int M = countl + countr + 1;

	int cubil = 0, cubir = 0, cubid = 0, cubiu = 0;

	while (X0 - 2*M*(cubil + 1) > 0 && examine(X0 - 2*M*(cubil + 1), Y0))
		++cubil;
	while (X0 + 2*M*(cubir + 1) <= N && examine(X0 + 2*M*(cubir + 1), Y0))
		++cubir;
	while (Y0 - 2*M*(cubid + 1) > 0 && examine(X0, Y0 - 2*M*(cubid + 1)))
		++cubid;
	while (Y0 + 2*M*(cubiu + 1) <= N && examine(X0, Y0 + 2*M*(cubiu + 1)))
		++cubiu;

	int xc = ((X0 + 2*M*cubir) + (X0 - 2*M*cubil)) / 2 + (M + 1)/2 - countl - 1;
	int yc = ((Y0 + 2*M*cubiu) + (Y0 - 2*M*cubid)) / 2 + (M + 1)/2 - countd - 1;
	solution(xc, yc);
}

• 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: 0 / 10
• Subtask 10: 0 / 10