제출 #197544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197544		SamAnd	Aliens (IOI07_aliens)	C++17	100 / 100	5 ms	396 KiB

aliens

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 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