Submission #85936

#	Time	Username	Problem	Language	Result	Execution time	Memory
85936		shoemakerjo	Aliens (IOI07_aliens)	C++14	100 / 100	3 ms	604 KiB

aliens

#include <bits/stdc++.h>

using namespace std;
#define x0 xxxxxx
#define y0 yyyyyy
#define int long long

int N, x0, y0;

int numq = 0;
// bool finbad = false;

bool isin(int xx, int yy) {

	if (0 >= xx || xx > N) return false;
	if (yy <= 0 || yy > N) return false;

	numq++;
	if (numq > 300) {
		// cout << "solution " << 1 << " " << 1 << endl;
		// assert(false);
	}

	cout << "examine " << xx << " " << yy << endl;
	cout.flush();
	string ans;
	cin >> ans;
	return ans == "true";
}

 main() {
	cin >> N >> x0 >> y0;
	//do left and right
	//need to find last guy that is a hit or something 
	//can binary search to the edge of this

	int nx, ny, lx, ly; //next x, next y, last x, last y

	int lo = x0;
	int hi = N;

	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		if (isin(mid, y0)) {
			lo = mid;
		}
		else {
			hi = mid-1;
		}
	}
	nx = lo;

	hi = x0;
	lo = 1;
	while (lo < hi) {
		int mid = (lo+hi)/2;
		if (isin(mid, y0)) {
			hi = mid;
		}
		else {
			lo = mid+1;
		}
	}

	lx = lo;

	lo = y0;
	hi = N;
	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		if (isin(x0, mid)) {
			lo = mid;
		}
		else {
			hi = mid-1;
		}
	}
	ny = lo;

	hi = y0;
	lo = 1;

	while (lo < hi) {
		int mid = (lo+hi)/2;
		if (isin(x0, mid)) {
			hi = mid;
		}
		else {
			lo = mid+1;
		}
	}

	ly = lo;


	//now we have all the guys

	int xans, yans;

	int mcur = (lx+nx)/2;

	if (!isin(mcur, y0)) {
		int m = (nx-lx+1)/3;
		while (isin(nx + m*2, y0)) {
			nx += m*2;
		}
		while (isin(lx - m*2, y0)) {
			lx -= m*2;
		}

	}
	else {
		int m = (nx-lx+1);
		while (isin(nx + m*2, y0)) {
			nx += m*2;
		}
		while (isin(lx - m*2, y0)) {
			lx -= m*2;
		}

	}
	xans = (nx + lx)/2;

	mcur = (ly + ny)/2;

	if (!isin(x0, mcur)) {
		int m = (ny - ly + 1)/3;
		while (isin(x0, ny+m*2)) {
			ny += m*2;
		}
		while (isin(x0, ly - m*2)) {
			ly -= m*2;
		}
	}
	else {
		int m = (ny - ly + 1);
		while (isin(x0, ny+m*2)) {
			ny += m*2;
		}
		while (isin(x0, ly - m*2)) {
			ly -= m*2;
		}
	}
	yans = (ly + ny)/2;


	cout << "solution " << xans << " " << yans << endl;





}

Compilation message (stderr)

aliens.cpp:31:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main() {
       ^

• 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