oj.uz

Submission #881285

# Submission time Handle Problem Language Result Execution time Memory
881285 2023-12-01T03:40:37 Z GusterGoose27 Worm Worries (BOI18_worm) C++17
100 / 100
 707 ms 7548 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})];
}

int query(arr3 a) {
	return query(a[0], a[1], a[2]);
}

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

void make_answer(arr3 a) {
	return make_answer(a[0], a[1], a[2]);
}
 
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);
}

arr3 operator+(arr3 a, arr3 b) {
	return arr3({a[0]+b[0], a[1]+b[1], a[2]+b[2]});
}

vector<arr3> adj(6);

void sol3d() {
	assert(n == m); assert(m == k);
	int u = q/2;
	mt19937 gen(0);
	arr3 mx({-1, -1, -1});
	for (int i = 0; i < u; i++) {
		int x, y, z;
		do {
			x = gen()%n; y = gen()%n; z = gen()%n;
		} while (arr.find(arr3({x, y, z})) != arr.end());
		if (query(x, y, z) > query(mx)) mx = arr3({x, y, z});
	}
	adj[0] = arr3({1, 0, 0});
	adj[1] = arr3({-1, 0, 0});
	adj[2] = arr3({0, 1, 0});
	adj[3] = arr3({0, -1, 0});
	adj[4] = arr3({0, 0, 1});
	adj[5] = arr3({0, 0, -1});
	while (1) {
		arr3 nxt = mx;
		for (int i = 0; i < 6; i++) {
			if (query(mx+adj[i]) > query(nxt)) nxt = mx+adj[i];
		}
		if (nxt == mx) break;
		mx = nxt;
	}
	make_answer(mx);
}

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 0 ms 436 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 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 596 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 676 KB Output is correct
4 Correct 1 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 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 432 KB Output is correct
10 Correct 1 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 452 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 696 KB Output is correct
6 Correct 3 ms 452 KB Output is correct
7 Correct 3 ms 1200 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1760 KB Output is correct
2 Correct 19 ms 1216 KB Output is correct
3 Correct 17 ms 948 KB Output is correct
4 Correct 17 ms 976 KB Output is correct
5 Correct 16 ms 1280 KB Output is correct
6 Correct 14 ms 956 KB Output is correct
7 Correct 15 ms 952 KB Output is correct
8 Correct 14 ms 1464 KB Output is correct
9 Correct 16 ms 1200 KB Output is correct
10 Correct 17 ms 1228 KB Output is correct
11 Correct 14 ms 1060 KB Output is correct
12 Correct 14 ms 1732 KB Output is correct
13 Correct 13 ms 956 KB Output is correct
14 Correct 23 ms 756 KB Output is correct
15 Correct 17 ms 1264 KB Output is correct
16 Correct 15 ms 1524 KB Output is correct
17 Correct 18 ms 1244 KB Output is correct
18 Correct 17 ms 960 KB Output is correct
19 Correct 15 ms 988 KB Output is correct
20 Correct 15 ms 1256 KB Output is correct
21 Correct 16 ms 1464 KB Output is correct
22 Correct 13 ms 1224 KB Output is correct
23 Correct 15 ms 944 KB Output is correct
24 Correct 14 ms 1016 KB Output is correct
25 Correct 14 ms 948 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 4000 KB Output is correct
2 Correct 374 ms 5020 KB Output is correct
3 Correct 281 ms 3968 KB Output is correct
4 Correct 332 ms 4348 KB Output is correct
5 Correct 314 ms 4724 KB Output is correct
6 Correct 323 ms 4776 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 6056 KB Output is correct
2 Correct 516 ms 5676 KB Output is correct
3 Correct 503 ms 5780 KB Output is correct
4 Correct 502 ms 6508 KB Output is correct
5 Correct 471 ms 6888 KB Output is correct
6 Correct 468 ms 6540 KB Output is correct
7 Correct 489 ms 6644 KB Output is correct
8 Correct 707 ms 7548 KB Output is correct
9 Correct 567 ms 6652 KB Output is correct
10 Correct 553 ms 6040 KB Output is correct
11 Correct 535 ms 6292 KB Output is correct