oj.uz

Submission #85934

# Submission time Handle Problem Language Result Execution time Memory
85934 2018-11-23T05:46:38 Z shoemakerjo Aliens (IOI07_aliens) C++14
80 / 100
 1000 ms 548 KB 
#include <bits/stdc++.h>

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

int N, x0, y0;

int numq = 0;

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

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

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





}

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 324 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 548 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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