oj.uz

Submission #108917

# Submission time Handle Problem Language Result Execution time Memory
108917 2019-05-02T17:14:06 Z MetB Aliens (IOI07_aliens) C++14
80 / 100
 1000 ms 412 KB 
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>

typedef long long ll;

const ll MOD = 1e9 + 7, INF = 1e18;

using namespace std;

ll n, x, y, min_x, max_x, min_y, max_y;

bool query (ll x, ll y)
{
	if (x <= 0 || x > n || y <= 0 || y > n) return false;
	cout << "examine " << x << ' ' << y << endl;
	fflush (stdout);

	string s;

	cin >> s;

	if (s == "true") return true;
	else return false;
}

int main ()
{
	cin >> n >> x >> y;

	max_x = min_x = x;
	max_y = min_y = y;

	int p = 1;

	while (query (x + p, y))
	{
		p *= 2;
	}

	int l = x + p / 2, r = x + p;

	while (l < r)
	{
		int mid = (l + r + 1) / 2;

		if (query (mid, y)) l = mid;
		else r = mid - 1;
	}

	max_x = l;

	p = 1;

	while (query (x - p, y))
	{
		p *= 2;
	}

	l = x - p, r = x - p / 2;

	while (l < r)
	{
		int mid = (l + r) / 2;

		if (query (mid, y)) r = mid;
		else l = mid + 1;
	}

	min_x = l;

	p = 1;

	while (query (x, y + p))
	{
		p *= 2;
	}

	l = y + p / 2, r = y + p;

	while (l < r)
	{
		int mid = (l + r + 1) / 2;

		if (query (x, mid)) l = mid;
		else r = mid - 1;
	}

	max_y = l;

	p = 1;

	while (query (x, y - p))
	{
		p *= 2;
	}

	l = y - p, r = y - p / 2;

	while (l < r)
	{
		int mid = (l + r) / 2;

		if (query (x, mid)) r = mid;
		else l = mid + 1;
	}

	min_y = l;

	ll m = max_x - min_x + 1;

	x = (min_x + max_x) / 2;
	y = (min_y + max_y) / 2;

	int min_xc = x, min_yc = y, max_xc = x, max_yc = y;

	while (query (min_xc, y - 2 * m) || query (min_xc, y) || query (min_xc, y + 2 * m)) min_xc -= 2 * m;
	while (query (max_xc, y - 2 * m) || query (max_xc, y) || query (max_xc, y + 2 * m)) max_xc += 2 * m;
	while (query (x - 2 * m, min_yc) || query (x, min_yc) || query (x + 2 * m, min_yc)) min_yc -= 2 * m;
	while (query (x - 2 * m, max_yc) || query (x, max_yc) || query (x + 2 * m, max_yc)) max_yc += 2 * m;


	int x_c = (max_xc + min_xc) / 2, y_c = (max_yc + min_yc) / 2;
	cout << "solution " << x_c << ' ' << y_c << endl;
	fflush (stdout);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Execution timed out 3029 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Execution timed out 3020 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -