oj.uz

Submission #197544

# Submission time Handle Problem Language Result Execution time Memory
197544 2020-01-21T15:59:42 Z SamAnd Aliens (IOI07_aliens) C++17
100 / 100
 5 ms 396 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <memory>
using namespace std;
#define m_p make_pair
#define int long long
const int N = 100005;

int n;

bool stg(int x, int y)
{
	if (y > n || x > n || x < 1 || y < 1)
		return false;
	cout << "examine " << x << ' ' << y << endl;
	string s;
	cin >> s;
	return s == "true";
}

int m;
int x0, yo;
int minx, maxx, miny, maxy;

int bynx1(int l, int r)
{
	while ((r - l) > 4)
	{
		int mid = (l + r) / 2;
		if (stg(mid, yo))
			l = mid;
		else
			r = mid;
	}
	for (int mid = r; mid >= l; --mid)
		if (stg(mid, yo))
			return mid;
}

int bynx2(int l, int r)
{
	while ((r - l) > 4)
	{
		int mid = (l + r) / 2;
		if (stg(mid, yo))
			r = mid;
		else
			l = mid;
	}
	for (int mid = l; mid <= r; ++mid)
		if (stg(mid, yo))
			return mid;
}

int byny1(int l, int r)
{
	while ((r - l) > 4)
	{
		int mid = (l + r) / 2;
		if (stg(x0, mid))
			l = mid;
		else
			r = mid;
	}
	for (int mid = r; mid >= l; --mid)
		if (stg(x0, mid))
			return mid;
}

int32_t main()
{
	//freopen("input.txt","r",stdin);
	cin >> n >> x0 >> yo;
	/////////////////////////////////
	int x = x0;
	int t = 0;
	maxx = x0;
	while (1)
	{
		if (x + (1LL << t) <= n && stg(x + (1LL << t), yo))
		{
			maxx = x + (1LL << t);
			++t;
		}
		else
		{
			maxx = bynx1(x, x+(1 << t));
			break;
		}
	}
	x = x0;
	t = 0;
	minx = x0;
	while (1)
	{
		if (x - (1LL << t) >= 1 && stg(x - (1LL << t), yo))
		{
			minx = x - (1LL << t);
			++t;
		}
		else
		{
			minx = bynx2(x - (1LL << t), x);
			break;
		}
	}
	m = maxx - minx + 1;
	//////////////
	int y = yo;
	t = 0;
	maxy = yo;
	while (1)
	{
		if (y + (1LL << t) <= n && stg(x0, y + (1LL << t)))
		{
			maxy = y + (1LL << t);
			++t;
		}
		else
		{
			maxy = byny1(y, y + (1LL << t));
			break;
		}
	}
	/*y=yo;
	t=0;
	miny=yo;
	while(1)
	{
	if(y-(1LL<<t)>=1 && stg(x0,y-(1LL<<t)))
	{
	miny=y-(1LL<<t);
	++t;
	}
	else
	{
	if(t==0)
	break;
	y=y-(1LL<<(t-1));
	t=0;
	}
	}*/
	miny = maxy - m + 1;
	/////////////////////////////////
	x = maxx;
	while (1)
	{
		if (x + m + m>n)
			break;
		if (!stg(x + m + m, yo))
			break;
		x += m;
		x += m;
		maxx = x;
	}
	x = minx;
	while (1)
	{
		if (x - m - m<1)
			break;
		if (!stg(x - m - m, yo))
			break;
		x -= m;
		x -= m;
		minx = x;
	}
	y = maxy;
	while (1)
	{
		if (y + m + m>n)
			break;
		if (!stg(x0, y + m + m))
			break;
		y += m;
		y += m;
		maxy = y;
	}
	y = miny;
	while (1)
	{
		if (y - m - m<1)
			break;
		if (!stg(x0, y - m - m))
			break;
		y -= m;
		y -= m;
		miny = y;
	}
	//assert(maxx - minx + 1 <= m * 5);
	cout << "solution " << (minx + maxx) / 2 << ' ' << (miny + maxy) / 2 << endl;
	return 0;
}

Compilation message

aliens.cpp: In function 'long long int bynx1(long long int, long long int)':
aliens.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
aliens.cpp: In function 'long long int bynx2(long long int, long long int)':
aliens.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
aliens.cpp: In function 'long long int byny1(long long int, long long int)':
aliens.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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