oj.uz

Submission #109708

# Submission time Handle Problem Language Result Execution time Memory
109708 2019-05-07T15:17:33 Z atoiz Worm Worries (BOI18_worm) C++14
100 / 100
 1114 ms 502628 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4224 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 6 ms 4224 KB Output is correct
5 Correct 8 ms 4352 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 6 ms 4224 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 6 ms 4268 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 7 ms 4224 KB Output is correct
9 Correct 5 ms 4224 KB Output is correct
10 Correct 6 ms 4224 KB Output is correct
11 Correct 6 ms 4352 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 12 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4224 KB Output is correct
2 Correct 28 ms 4272 KB Output is correct
3 Correct 21 ms 4352 KB Output is correct
4 Correct 21 ms 4352 KB Output is correct
5 Correct 18 ms 4352 KB Output is correct
6 Correct 30 ms 4224 KB Output is correct
7 Correct 17 ms 4252 KB Output is correct
8 Correct 13 ms 4224 KB Output is correct
9 Correct 31 ms 4224 KB Output is correct
10 Correct 19 ms 4352 KB Output is correct
11 Correct 15 ms 4224 KB Output is correct
12 Correct 37 ms 4224 KB Output is correct
13 Correct 25 ms 4224 KB Output is correct
14 Correct 33 ms 4352 KB Output is correct
15 Correct 15 ms 4224 KB Output is correct
16 Correct 25 ms 4224 KB Output is correct
17 Correct 17 ms 4224 KB Output is correct
18 Correct 35 ms 4224 KB Output is correct
19 Correct 23 ms 4472 KB Output is correct
20 Correct 20 ms 4352 KB Output is correct
21 Correct 32 ms 4224 KB Output is correct
22 Correct 28 ms 4224 KB Output is correct
23 Correct 28 ms 4224 KB Output is correct
24 Correct 32 ms 4352 KB Output is correct
25 Correct 26 ms 4224 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 4780 KB Output is correct
2 Correct 233 ms 4736 KB Output is correct
3 Correct 358 ms 4780 KB Output is correct
4 Correct 368 ms 4984 KB Output is correct
5 Correct 415 ms 4736 KB Output is correct
6 Correct 415 ms 4776 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 502440 KB Output is correct
2 Correct 1102 ms 502628 KB Output is correct
3 Correct 1114 ms 502436 KB Output is correct
4 Correct 1020 ms 502376 KB Output is correct
5 Correct 995 ms 502432 KB Output is correct
6 Correct 972 ms 502460 KB Output is correct
7 Correct 956 ms 502440 KB Output is correct
8 Correct 943 ms 502376 KB Output is correct
9 Correct 1018 ms 502376 KB Output is correct
10 Correct 1067 ms 502544 KB Output is correct
11 Correct 1063 ms 502384 KB Output is correct