Submission #109708

#	Time	Username	Problem	Language	Result	Execution time	Memory
109708		atoiz	Worm Worries (BOI18_worm)	C++14	100 / 100	1114 ms	502628 KiB

worm

// spoiled

#include <iostream>
#include <vector>
#include <cstring>
#include <random>
#include <algorithm>
#include <chrono>
#include <cassert>

using namespace std;

namespace Subtask1D
{

	const double RATIO = 1 - 2 / (1 + sqrt(5));

	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 = 0, r = N+1, ml = l + (r - l) * RATIO, mr = r - int((r - l) * RATIO);
		while (l < ml && ml < mr && mr < r) {
			if (get(ml) < get(mr)) l = ml, ml = mr, mr = r - int((r - l) * RATIO);
			else r = mr, mr = ml, ml = l + (r - l) * RATIO;
		}
		for (int i = l + 1; i < r; ++i) {
			if (get(i) >= get(i-1) && get(i) >= get(i+1)) {
				cout << "! " << i << " 1 1" << endl;
				return;
			}
		}

		assert(0);
	}
}

namespace Subtask2D
{
	vector< vector<int> > A;

	int N, M, Q;

	int get(int i, int j)
	{
		if (0 >= i || i > N || 0 >= j || j > M) return 0;
		if (A[i][j]) return A[i][j];
		// return A[i][j] = 10000 - abs(i - 214) - abs(j - 532);
		cout << "? " << i << ' ' << j << " 1" << endl;
		cin >> A[i][j];
		return A[i][j];
	}

	void run(int _N, int _M, int _Q)
	{
		N = _N, M = _M, Q = _Q;
		A.assign(N + 1, vector<int>(M + 1, 0));
		int li = 1, ri = N, lj = 1, rj = M, maxi = 0, maxj = 1;

		while (li < ri || lj < rj) {
			if (li < ri) {
				int mi = (li + ri) >> 1, mj = rj;
				for (int j = lj; j < rj; ++j) {
					if (get(mi, mj) <= get(mi, j)) mj = j;
				}

				if (get(mi, mj) <= get(maxi, maxj)) {
					if (mi < maxi) li = mi + 1;
					else ri = mi - 1;
				} else if (get(mi, mj) < get(mi + 1, mj)) {
					maxi = mi, maxj = mj;
					li = mi + 1;
				} else if (get(mi, mj) < get(mi - 1, mj)) {
					maxi = mi, maxj = mj;
					ri = mi - 1;
				} else {
					assert(get(mi, mj) >= get(mi, mj - 1) && get(mi, mj) >= get(mi, mj + 1));
					cout << "! " << mi << ' ' << mj << " 1" << endl;
					return;
				}
			}

			if (lj < rj) {
				int mj = (lj + rj) >> 1, mi = ri;
				for (int i = li; i < ri; ++i) {
					if (get(mi, mj) <= get(i, mj)) mi = i;
				}

				if (get(mi, mj) <= get(maxi, maxj)) {
					if (mj < maxj) lj = mj + 1;
					else rj = mj - 1;
				} else if (get(mi, mj) < get(mi, mj + 1)) {
					maxi = mi, maxj = mj;
					lj = mj + 1;
				} else if (get(mi, mj) < get(mi, mj - 1)) {
					maxi = mi, maxj = mj;
					rj = mj - 1;
				} else {
					assert(get(mi, mj) >= get(mi - 1, mj) && get(mi, mj) >= get(mi + 1, mj));
					cout << "! " << mi << ' ' << mj << " 1" << endl;
					return;	
				}
			}
		}

		cout << "! " << li << ' ' << lj << " 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) Subtask3D::run(N, M, K, Q);
	else if (M > 1) Subtask2D::run(N, M, Q);
	else Subtask1D::run(N, Q);
}

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