Submission #886880

#TimeUsernameProblemLanguageResultExecution timeMemory
886880rxlfd314Worm Worries (BOI18_worm)C++17
0 / 100
1 ms708 KiB
#include <bits/stdc++.h>
using namespace std;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand_() {
	return uniform_int_distribution<int>(0, INT_MAX)(rng);
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, M, K, Q;
  cin >> N >> M >> K >> Q;
	map<ari3, int> done;
	auto ask = [&](int a, int b, int c) {
		if (done.find({a, b, c}) != end(done))
			return done[{a, b, c}];
		if (a < 0 || a >= N || b < 0 || b >= M || c < 0 || c >= K)
			return 0;
      cout << "? " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl;
		int ret;
      cin >> ret;
		done[{a, b, c}] = ret;
		return a;
	};
	auto good = [&](int a, int b, int c) {
		int v = ask(a, b, c);
		if (ask(a-1, b, c) > v)
			return ari3{a-1, b, c};
		if (ask(a+1, b, c) > v)
			return ari3{a+1, b, c};
		if (ask(a, b-1, c) > v)
			return ari3{a, b-1, c};
		if (ask(a, b+1, c) > v)
			return ari3{a, b+1, c};
		if (ask(a, b, c-1) > v)
			return ari3{a, b, c-1};
		if (ask(a, b, c+1) > v)
			return ari3{a, b, c+1};
		return ari3{-1, -1, -1};
	};
	// choose random X times, go Y steps each time
	const int X = 20, Y = Q / (8 * X);
	FOR(_, 1, X) {
		int a = rand_() % N, b = rand_() % M, c = rand_() % K;
		FOR(__, 1, Y) {
#ifdef DEBUG
			cout << "current: " << a << ' ' << b << ' ' << c << endl;
#endif
			auto [d, e, f] = good(a, b, c);
			if (d < 0 && e < 0 && f < 0) {
              cout << "! " << a + 1 << ' ' << b + 1 << ' ' << c + 1 << endl;
				return 0;
			}
			a = d, b = e, c = f;
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...