Submission #881285

#	Time	Username	Problem	Language	Result	Execution time	Memory
881285		GusterGoose27	Worm Worries (BOI18_worm)	C++17	100 / 100	707 ms	7548 KiB

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})];
}

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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23