oj.uz

Submission #769494

# Submission time Handle Problem Language Result Execution time Memory
769494 2023-06-29T16:06:27 Z eliasol Aliens (IOI07_aliens) C++14
100 / 100
 2 ms 208 KB 
#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>

#define int long long

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;
}

signed 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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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