Submission #539452

#	Time	Username	Problem	Language	Result	Execution time	Memory
539452		skittles1412	Worm Worries (BOI18_worm)	C++17	36 / 100	1530 ms	1014268 KiB

worm

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

namespace s1 {

bool solve(int n, int m, int k, int q) {
#ifdef GEN
	int ogrid[n];
	mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
	for (auto& a : ogrid) {
		a = int(cowng() % int(1e9));
	}
#endif
	if (m != 1 || k != 1) {
		return false;
	}
	int cache[n];
	memset(cache, -1, sizeof(cache));
	auto queryuc = [&](int i) -> int {
#ifndef GEN
		cout << "? " << i + 1 << " 1 1" << endl;
		int x;
		cin >> x;
		return x;
#else
		return ogrid[i];
#endif
	};
	auto query = [&](int i) -> int {
		if (!(0 <= i && i < n)) {
			return -1e9;
		}
		if (cache[i] != -1) {
			return cache[i];
		}
		static int qcnt = 0;
		qcnt++;
		assert(qcnt <= q);
		return cache[i] = queryuc(i);
	};
	auto answer = [&](int i) -> void {
		cout << "! " << i + 1 << " 1 1" << endl;
		exit(0);
	};
	auto check = [&](int i) -> void {
		if (query(i) >= max(query(i - 1), query(i + 1))) {
			dbg(query(i), query(i - 1), query(i + 1));
			answer(i);
		}
	};
	int l = 0, r = n - 1;
	while ((r - l + 1) > 3) {
		int madd = (r - l + 1) / 3, m1 = l + madd, m2 = r - madd;
		dbg(l, r, m1, m2);
		int a = query(m1), b = query(m2);
		if (a < b) {
			l = m1;
		} else if (a == b) {
			l = m1;
			r = m2;
		} else if (a > b) {
			r = m2;
		}
	}
	if (l == r) {
		answer(l);
	} else if (l + 1 == r) {
		check(l);
		answer(r);
	} else {
		check(l + 1);
		check(l);
		answer(r);
	}
	return true;
}

}  // namespace s1

//#define GEN

namespace s3 {

const int dx[] = {0, 0, 0, 0, -1, 1}, dy[] = {0, 0, -1, 1, 0, 0}, dz[] = {-1, 1, 0, 0, 0, 0};

bool solve(int n, int m, int l, int q) {
	auto ibs = [&](int x, int y, int z) -> bool {
		return 0 <= x && x < n && 0 <= y && y < m && 0 <= z && z < l;
	};
#ifdef GEN
	vector<vector<vector<int>>> arrv(n, vector<vector<int>>(m, vector<int>(l, 1)));
	{
		mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
		if (l == 1) {
			int cind = 2;
			auto set = [&](int x, int y, int v) -> void {
				if (x < n && y < m) {
					arrv[x][y][0] = v;
				}
			};
			for (int i = 0; i < n;) {
				for (int j = 0; j < m; j++) {
					set(i, j, cind++);
				}
				i++;
				set(i, m - 1, cind++);
				i++;
				for (int j = m - 1; j >= 0; j--) {
					set(i, j, cind++);
				}
				i++;
				set(i, 0, cind++);
				i++;
			}
		} else {
			for (auto& a : arrv) {
				for (auto& b : a) {
					for (auto& c : b) {
						c = cowng() % int(1e9);
					}
				}
			}
		}
	}
#endif
	vector<vector<vector<int>>> cache(n, vector<vector<int>>(m, vector<int>(l, -1)));
	int queries = 0;
	auto query = [&](int x, int y, int z) -> int {
		int& ans = cache[x][y][z];
		if (ans != -1) {
			return ans;
		}
		queries++;
#ifndef GEN
		cout << "? " << x + 1 << " " << y + 1 << " " << z + 1 << endl;
		cin >> ans;
#else
		ans = arrv[x][y][z];
#endif
		return ans;
	};
	auto answer = [&](int x, int y, int z) -> void {
#ifdef GEN
		cout << "queries: " << queries << endl;
#endif
		cout << "! " << x + 1 << " " << y + 1 << " " << z + 1 << endl;
		exit(0);
	};
	mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());
	pair<int, array<int, 3>> opt {-1, {0, 0, 0}};
	int iter = 500;
	if (q == 3500) {
		iter = 10000;
	}
	auto upd = [&](int x, int y, int z) -> void {
		opt = max(opt, pair<int, array<int, 3>> {query(x, y, z), {x, y, z}});
	};
	for (int x: {0, n / 2, n - 1}) {
		for (int y: {0, m / 2, m - 1}) {
			for (int z: {0, l / 2, l - 1}) {
				upd(x, y, z);
			}
		}
	}
	for (int i = 0; i < iter; i++) {
		int x = cowng() % n, y = cowng() % m, z = cowng() % l;
		upd(x, y, z);
	}
	auto [x, y, z] = opt.second;
	while (true) {
		for (int k = 0; k < 6; k++) {
			int cx = x + dx[k], cy = y + dy[k], cz = z + dz[k];
			if (ibs(cx, cy, cz)) {
				if (query(cx, cy, cz) > query(x, y, z)) {
					tie(x, y, z) = tie(cx, cy, cz);
					goto loop;
				}
			}
		}
		answer(x, y, z);
	loop:;
	}
}

}  // namespace s3

void solve() {
	int n, m, k, q;
	cin >> n >> m >> k >> q;
	s1::solve(n, m, k, q) || s3::solve(n, m, k, q);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 22
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 0 / 23