Submission #881279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881279	2023-12-01T03:18:36 Z	GusterGoose27	Worm Worries (BOI18_worm)	C++17	44 / 100	18 ms	1596 KB

worm

#include <bits/stdc++.h>

using namespace std;

int n, m, k, q;
typedef array<int, 3> arr3;

map<arr3, int> arr;

int query(int i, int j = 0, int k = 0) {
	if (i < 0 || i >= n || j < 0 || j >= m || k < 0 || k >= m) return 0;
	if (arr.find(arr3({i, j, k})) == arr.end()) {
		q--;
		assert(q >= 0);
		cout << "? " << i+1 << ' ' << j+1 << ' ' << k+1 << endl;
		cin >> arr[arr3({i, j, k})];
	}
	return arr[arr3({i, j, k})];
}

void make_answer(int i, int j = 0, int k = 0) {
	cout << "! " << i+1 << ' ' << j+1 << ' ' << k+1 << '\n';
}

void sol1d() {
	assert(m == 1); assert(k == 1);
	int l = -1, r = n;
	while (r > l) {
		if (r-l == 1) {
			if (query(r) > query(l)) l = r;
			else r = l;
		}
		else if (r-l == 2) {
			query(l+1);
			int v = l;
			for (int i = l+1; i <= r; i++) if (query(i) > query(v)) v = i;
			l = r = v;
		}
		else if (r-l == 3) {
			if (query(l) >= query(r)) {
				if (query(l) >= query(l+1)) r = l;
				else if (query(l+1) >= query(l+2)) l = r = l+1;
				else if (query(l+2) >= query(r)) l = r;
			}
			else {
				if (query(r) >= query(r-1)) l = r;
				else if (query(r-1) >= query(r-2)) l = r = r-1;
				else if (query(r-2) >= query(l)) r = l;
			}
		}
		else {
			if (query(l) < query(r)) { // right thing has to be strictly greater
				int i = r-(r-l+2)/3;
				int j = (l+i+1)/2;
				if (query(i) < query(r)) {
					l = i;
				}
				else {
					if (query(i) > query(j)) {
						if (query(i+1) > query(i)) l = i+1;
						else {
							l = j;
							r = i;
						}
					}
					else {
						if (query(j-1) >= query(j)) {
							r = j-1;
						}
						else {
							l = j;
							r = i;
						}
					}
				}
			}
			else { // right thing has to be strictly greater
				int i = l+(r-l+2)/3;
				int j = (r+i)/2;
				if (query(i) <= query(l)) {
					r = i;
				}
				else {
					if (query(i) >= query(j)) {
						if (query(i-1) >= query(i)) r = i-1;
						else {
							l = i;
							r = j;
						}
					}
					else {
						if (query(j+1) > query(j)) {
							l = j+1;
						}
						else {
							l = i;
							r = j;
						}
					}
				}
			}
			//  = (query(l) >= query(r) ?  : r-(r-l+2)/3);
			// int j = (query(l) >= query(r) ? (r+i)/2 : (l+i)/2);
			// if (query(i))
		}
	}
	make_answer(l);
}

void sol2d() {
	assert(n == m); assert(k == 1);
	int x1 = -1, x2 = n, y1 = -1, y2 = n;
	while (x1+1 < x2 && y1+1 < y2) {
		//if (x2 - x1 < y2-y1) {
			int y = (y1+y2)/2;
			int v = x1;
			for (int i = x1; i <= x2; i++) {
				if (query(i, y) > query(v, y)) v = i;
			}
			if (query(v, y) >= query(v, y+1)) y2 = y;
			else y1 = y+1;
		/*}
		else {
			int x = (x1+x2)/2;
			int v = y1;
			for (int i = y1; i <= y2; i++) {
				if (query(x, i) > query(x, v)) v = i;
			}
			if (query(x, v) >= query(x+1, v)) x2 = x;
			else x1 = x+1;
		}*/
	}
	int a = x1, b = y1;
	for (int i = x1; i <= x2; i++) {
		for (int j = y1; j <= y2; j++) {
			if (query(i, j) > query(a, b)) {
				a = i; b = j;
			}
		}
	}
	make_answer(a, b);
}

void sol3d() {
	assert(false);
}

int main() {
	cin >> n >> m >> k >> q;
	if (m == 1 && k == 1) sol1d();
	else if (k == 1) sol2d();
	else sol3d();
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	440 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	432 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	440 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	400 KB	Output is correct
2	Correct	1 ms	440 KB	Output is correct
3	Correct	0 ms	436 KB	Output is correct
4	Correct	0 ms	436 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	596 KB	Output is correct
8	Correct	0 ms	420 KB	Output is correct
9	Correct	1 ms	436 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	436 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1196 KB	Output is correct
2	Correct	8 ms	984 KB	Output is correct
3	Correct	6 ms	1200 KB	Output is correct
4	Correct	11 ms	944 KB	Output is correct
5	Correct	7 ms	1488 KB	Output is correct
6	Correct	8 ms	960 KB	Output is correct
7	Correct	8 ms	1204 KB	Output is correct