oj.uz

Submission #881282

# Submission time Handle Problem Language Result Execution time Memory
881282 2023-12-01T03:31:51 Z GusterGoose27 Worm Worries (BOI18_worm) C++17
63 / 100
 21 ms 1796 KB 
#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;
	int mxa = -1, mxb = -1;
	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;
			}
			/*
			extra condition -- if cur global max is > than max discovered,
			we choose the side with global max on it
			*/
			if (query(mxa, mxb) >= query(v, y)) {
				if (mxb <= y) y2 = y;
				else y1 = y;
			}
			else {
				mxa = v;
				mxb = y;
				if (query(v, y) >= query(v, y+1)) y2 = y;
				else y1 = y; // not worth it
			}
		}
		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(mxa, mxb) >= query(x, v)) {
				if (mxa <= x) x2 = x;
				else x1 = x;
			}
			else {
				mxa = x;
				mxb = v;
				if (query(x, v) >= query(x+1, v)) x2 = x;
				else x1 = x; // not worth it
			}
		}
	}
	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 436 KB Output is correct
2 Correct 1 ms 440 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 436 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 696 KB Output is correct
2 Correct 3 ms 692 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 4 ms 1456 KB Output is correct
5 Correct 3 ms 948 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 4 ms 944 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1220 KB Output is correct
2 Correct 15 ms 1460 KB Output is correct
3 Correct 19 ms 704 KB Output is correct
4 Correct 16 ms 1484 KB Output is correct
5 Correct 18 ms 1740 KB Output is correct
6 Correct 13 ms 1732 KB Output is correct
7 Correct 21 ms 972 KB Output is correct
8 Correct 15 ms 948 KB Output is correct
9 Correct 14 ms 1492 KB Output is correct
10 Correct 15 ms 1000 KB Output is correct
11 Correct 17 ms 948 KB Output is correct
12 Correct 18 ms 1764 KB Output is correct
13 Correct 15 ms 1212 KB Output is correct
14 Correct 18 ms 1796 KB Output is correct
15 Correct 15 ms 1056 KB Output is correct
16 Correct 15 ms 1248 KB Output is correct
17 Correct 16 ms 1068 KB Output is correct
18 Correct 17 ms 1224 KB Output is correct
19 Correct 17 ms 1040 KB Output is correct
20 Correct 15 ms 600 KB Output is correct
21 Correct 14 ms 1212 KB Output is correct
22 Correct 13 ms 1452 KB Output is correct
23 Correct 21 ms 1280 KB Output is correct
24 Correct 18 ms 1216 KB Output is correct
25 Correct 13 ms 948 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -