oj.uz

Submission #756083

# Submission time Handle Problem Language Result Execution time Memory
756083 2023-06-11T05:13:36 Z SanguineChameleon Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 208 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

#define int long long

namespace judge {
	int n, m, sx, sy, cx, cy, lx, ly;

	void init() {
		#ifdef KAMIRULEZ
			cin >> n >> m >> sx >> sy >> cx >> cy;
			lx = cx - m / 2 - m * 2;
			ly = cy - m / 2 - m * 2;
		#endif
	}

	bool query(int qx, int qy) {
		for (int i = 0; i < 5; i++) {
			for (int j = i & 1; j < 5; j += 2) {
				if (lx + i * m <= qx && qx < lx + (i + 1) * m && ly + j * m <= qy && qy < ly + (j + 1) * m) {
					return true;
				}
			}
		}
		return false;
	}
}

namespace contestant {
	int n, sx, sy;

	void init() {
		#ifdef KAMIRULEZ
			n = judge::n;
			sx = judge::sx;
			sy = judge::sy;
		#else
			cin >> n >> sx >> sy;
		#endif
	}

	bool query(int qx, int qy) {
		if (qx < 1 || qx > n || qy < 1 || qy > n) {
			return false;
		}
		cout << "examine" << " " << qx << " " << qy << endl;
		#ifdef KAMIRULEZ
			return judge::query(qx, qy);
		#else
			string res;
			cin >> res;
			return (res == "true");
		#endif
	}


	void solve() {
		int lx = -1;
		if (query(1, sy)) {
			lx = 1;
		}
		else {
			int lt = 1;
			int rt = sx;
			while (rt - lt > 1) {
				int mt = (lt + rt) / 2;
				if (query(mt, sy)) {
					rt = mt;
				}
				else {
					lt = mt;
				}
			}
			lx = rt;
		}
		int rx = -1;
		if (query(n, sy)) {
			rx = n;
		}
		else {
			int lt = sx;
			int rt = n;
			while (rt - lt > 1) {
				int mt = (lt + rt) / 2;
				if (query(mt, sy)) {
					lt = mt;
				}
				else {
					rt = mt;
				}
			}
			rx = lt;
		}
		int ly = -1;
		if (query(sx, 1)) {
			ly = 1;
		}
		else {
			int lt = 1;
			int rt = sy;
			while (rt - lt > 1) {
				int mt = (lt + rt) / 2;
				if (query(sx, mt)) {
					rt = mt;
				}
				else {
					lt = mt;
				}
			}
			ly = rt;
		}
		int ry = -1;
		if (query(sx, n)) {
			ry = n;
		}
		else {
			int lt = sy;
			int rt = n;
			while (rt - lt > 1) {
				int mt = (lt + rt) / 2;
				if (query(sx, mt)) {
					lt = mt;
				}
				else {
					rt = mt;
				}
			}
			ry = lt;
		}
		int m = rx - lx + 1;
		if (m % 5 == 0 && !query(lx + m / 5, sy)) {
			m /= 5;
		}
		else if (m % 3 == 0 && !query(lx + m / 3, sy)) {
			m /= 3;
		}
		while (query(lx - m * 2, sy)) {
			lx -= m * 2;
		}
		while (query(rx + m * 2, sy)) {
			rx += m * 2;
		}
		if (rx - lx + 1 == m * 3) {
			lx -= m;
			rx += m;
		}
		while (query(sx, ly - m * 2)) {
			ly -= m * 2;
		}
		while (query(sx, ry + m * 2)) {
			ry += m * 2;
		}
		if (ry - ly + 1 == m * 3) {
			ly -= m;
			ry += m;
		}
		int cx = lx + m / 2 + m * 2;
		int cy = ly + m / 2 + m * 2;
		cout << "solution" << " " << cx << " " << cy << endl;
	}
}

void just_do_it() {
	judge::init();
	contestant::init();
	contestant::solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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