oj.uz

Submission #881284

# Submission time Handle Problem Language Result Execution time Memory
881284 2023-12-01T03:40:07 Z GusterGoose27 Worm Worries (BOI18_worm) C++17
63 / 100
 543 ms 6212 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 = 1; 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 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 432 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 436 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 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 436 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 948 KB Output is correct
2 Correct 3 ms 708 KB Output is correct
3 Correct 3 ms 688 KB Output is correct
4 Correct 3 ms 696 KB Output is correct
5 Correct 3 ms 948 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 3 ms 692 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1720 KB Output is correct
2 Correct 14 ms 1204 KB Output is correct
3 Correct 18 ms 1776 KB Output is correct
4 Correct 15 ms 1316 KB Output is correct
5 Correct 15 ms 1212 KB Output is correct
6 Correct 16 ms 2056 KB Output is correct
7 Correct 13 ms 1016 KB Output is correct
8 Correct 13 ms 1480 KB Output is correct
9 Correct 16 ms 1216 KB Output is correct
10 Correct 13 ms 1476 KB Output is correct
11 Correct 13 ms 1232 KB Output is correct
12 Correct 15 ms 956 KB Output is correct
13 Correct 13 ms 1468 KB Output is correct
14 Correct 15 ms 1472 KB Output is correct
15 Correct 15 ms 1228 KB Output is correct
16 Correct 16 ms 1004 KB Output is correct
17 Correct 16 ms 1208 KB Output is correct
18 Correct 15 ms 1212 KB Output is correct
19 Correct 18 ms 1200 KB Output is correct
20 Correct 13 ms 1460 KB Output is correct
21 Correct 16 ms 1236 KB Output is correct
22 Correct 14 ms 948 KB Output is correct
23 Correct 16 ms 948 KB Output is correct
24 Correct 13 ms 1004 KB Output is correct
25 Correct 15 ms 692 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 4412 KB Output is correct
2 Incorrect 349 ms 4528 KB not a local maximum
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 5816 KB Output is correct
2 Correct 524 ms 6172 KB Output is correct
3 Correct 543 ms 5532 KB Output is correct
4 Incorrect 541 ms 6212 KB not a local maximum
5 Halted 0 ms 0 KB -