Submission #108825

#TimeUsernameProblemLanguageResultExecution timeMemory
108825atoizWorm Worries (BOI18_worm)C++14
59 / 100
1134 ms502464 KiB
#include <iostream>
#include <vector>
#include <cstring>
#include <random>
#include <algorithm>
#include <chrono>

using namespace std;

namespace Subtask1D
{
	int N;
	vector<int> A;

	int get(int i)
	{
		if (i <= 0 || i > N) return 0;
		if (A[i]) return A[i];
		cout << "? " << i << " 1 1" << endl;
		cin >> A[i];
		return A[i];
	}

	void run(int _N, int _Q)
	{
		N = _N;
		A.assign(N+1, 0);

		int l = 1, r = N;
		while (l < r) {
			int m = (l + r) >> 1;
			if (get(m) < get(m + 1)) {
				l = m + 1;
			} else r = m;
		}

		cout << "! " << l << " 1 1" << endl;
	}
}

namespace Subtask3D
{
	const int di[6] = {-1, 1, 0, 0, 0, 0}, dj[6] = {0, 0, -1, 1, 0, 0}, dk[6] = {0, 0, 0, 0, -1, 1};
	int dd[6] = {0, 1, 2, 3, 4, 5};
	vector< vector< vector<int> > > A;
	int N, M, K, Q;
	mt19937 rng(chrono::system_clock().now().time_since_epoch().count());
	uniform_int_distribution<int> rnd(1, 1e9);

	int rd(int l, int r) { return l + rnd(rng) % (r - l + 1); }

	int get(int i, int j, int k)
	{
		if (0 >= i || i > N || 0 >= j || j > M || 0 >= k || k > K) return 0;
		if (A[i][j][k]) return A[i][j][k];
		cout << "? " << i << ' ' << j << ' ' << k << endl;
		cin >> A[i][j][k];
		return A[i][j][k];
	}

	void run(int _N, int _M, int _K, int _Q)
	{
		N = _N, M = _M, K = _K, Q = _Q;
		A.assign(N+1, vector< vector<int> >(M+1, vector<int>(K+1, 0)));

		int i0 = 0, j0 = 0, k0 = 0;
		for (int _ = 0; _ < Q / 2; ++_) {
			int i = rd(1, N), j = rd(1, M), k = rd(1, K);
			if (get(i0, j0, k0) < get(i, j, k)) i0 = i, j0 = j, k0 = k;
		}

		while (true) {
			shuffle(dd, dd + 6, rng);

			int d = 0;
			for (; d < 6; ++d) {
				int i = i0 + di[dd[d]], j = j0 + dj[dd[d]], k = k0 + dk[dd[d]];
				if (get(i0, j0, k0) < get(i, j, k)) {
					i0 = i, j0 = j, k0 = k;
					break;
				}
			}

			if (d == 6) {
				cout << "! " << i0 << ' ' << j0 << ' ' << k0 << endl;
				return;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, M, K, Q; cin >> N >> M >> K >> Q;
	if (K > 1 || M > 1) Subtask3D::run(N, M, K, Q);
	else Subtask1D::run(N, Q);
}
#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...