Submission #1005357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005357		j_vdd16	Worm Worries (BOI18_worm)	C++17	100 / 100	1076 ms	10540 KiB

worm

#include <algorithm>
#include <array>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

int a, b, c, q;
void answer(int x, int y, int z)
{
	cout << "! " << x << ' ' << y << ' ' << z << endl;
}

map<tuple<int, int, int>, int> results;
inline int ask(int x, int y, int z)
{
	if (x <= 0 || x > a || y <= 0 || y > b || z <= 0 || z > c)
		return 1;

	if (results.count({ x, y, z }))
		return results[{x, y, z}];

	q--;
	if (q < 0)
	{
		answer(1, 1, 1);
		exit(0);
	}

	cout << "? " << x << ' ' << y << ' ' << z << endl;

	int res = x + y * z;
	cin >> res;
	results[{x, y, z}] = res;

	if (res == -1)
	{
		exit(1);
	}

	return res;
}
void solveGreedy()
{
	int x = 1, y = 1, z = 1;
	int d = floor(cbrt(q / 2));
	for (int i = 1; i <= d; i++)
	{
		for (int j = 1; j <= d; j++)
		{
			for (int k = 1; k <= d; k++)
			{
				if (ask(a / d * i, b / d * j, c / d * k) > ask(x, y, z))
				{
					x = a / d * i;
					y = b / d * j;
					z = c / d * k;
				}
			}
		}
	}

	while (true)
	{
		int val = ask(x, y, z);

		if (ask(x + 1, y, z) > val)
			x++;
		else if (ask(x - 1, y, z) > val)
			x--;
		else if (ask(x, y + 1, z) > val)
			y++;
		else if (ask(x, y - 1, z) > val)
			y--;
		else if (ask(x, y, z + 1) > val)
			z++;
		else if (ask(x, y, z - 1) > val)
			z--;
		else
			break;
	}

	answer(x, y, z);
}


inline int ask(const array<int, 3>& pos, const array<int, 3>& perm)
{
	return ask(pos[perm[0]], pos[perm[1]], pos[perm[2]]);
}

array<int, 3> solve(ii bx, ii by, ii bz, int maxX, int maxY, int maxZ, array<int, 3> perm)
{
	while (true)
	{
		int dx = bx.second - bx.first;
		int dy = by.second - by.first;
		int dz = bz.second - bz.first;
		if (dx <= 2 && dy <= 2 && dz <= 2)
		{
			array<int, 3> res = { maxX, maxY, maxZ };
			return { res[perm[0]], res[perm[1]], res[perm[2]] };
		}

		if (dy >= dx && dy >= dz)
		{
			swap(dx, dy);
			swap(bx, by);
			swap(maxX, maxY);

			if (perm[0] == 2)
				swap(perm[1], perm[2]);
			else if (perm[1] == 2)
				swap(perm[0], perm[2]);
			else
				swap(perm[0], perm[1]);
		}
		else if (dz >= dx && dz >= dy)
		{
			swap(dx, dz);
			swap(bx, bz);
			swap(maxX, maxZ);

			if (perm[0] == 1)
				swap(perm[1], perm[2]);
			else if (perm[1] == 1)
				swap(perm[0], perm[2]);
			else
				swap(perm[0], perm[1]);
		}

		int maxVal = ask({ maxX, maxY, maxZ }, perm);
		int x = bx.first + dx / 2;
		for (int y = by.first + 1; y < by.second; y++)
		{
			for (int z = bz.first + 1; z < bz.second; z++)
			{
				int val = ask({ x, y, z }, perm);
				if (val > maxVal)
				{
					maxVal = val;
					maxX = x;
					maxY = y;
					maxZ = z;
				}
			}
		}

		if (maxX != x)
		{
			if (maxX < x)
				bx.second = x;
			else
				bx.first = x;
		}
		else
		{
			int val1 = ask({ maxX - 1, maxY, maxZ }, perm);
			int val2 = ask({ maxX + 1, maxY, maxZ }, perm);
			if (maxVal >= val1 && maxVal >= val2)
			{
				array<int, 3> res = { maxX, maxY, maxZ };
				return { res[perm[0]], res[perm[1]], res[perm[2]] };
			}
			else if (val1 > maxVal)
			{
				bx.second = x;
				maxX -= 1;
			}
			else// if (val2 > maxVal)
			{
				bx.first = x;
				maxX += 1;
			}
		}
	}
}

signed main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);

	cin >> a >> b >> c >> q;
	
	if (a == 1 && b == 1 && c == 1)
	{
		answer(1, 1, 1);
	}
	else if (b == 1 && c == 1)
	{
		//f * f = (1 - f)
		//f^2 + f - 1 = 0
		//f = (-1 + sqrt(5)) / 2
		double f = (-1.0 + sqrt(5.0)) / 2.0;

		int l = 0, r = a + 1;
		int pos1 = -1, pos2 = -1;

		pos1 = l + (int)round(double(r - l) * (1 - f));
		pos2 = l + (int)round(double(r - l) * f);
		while (true)
		{
			if (r == l)
			{
				answer(l, 1, 1);
				break;
			}
			else if (r - l == 1)
			{
				if (ask(l, 1, 1) > ask(r, 1, 1))
					answer(l, 1, 1);
				else
					answer(r, 1, 1);

				break;
			}

			if (pos1 == -1)
				pos1 = l + (int)round(double(pos2 - l) * f);
			else if (pos2 == -1)
				pos2 = pos1 + (int)round(double(r - pos1) * (1 - f));

			int val1 = ask(pos1, 1, 1);
			int val2 = ask(pos2, 1, 1);

			if (val1 > val2)
			{
				r = pos2;
				pos2 = pos1;
				pos1 = -1;
			}
			else
			{
				l = pos1;
				pos1 = pos2;
				pos2 = -1;
			}
		}
	}
	else if (a == 1 || b == 1 || c == 1 || (a <= 100 && b <= 100 && c <= 100))
	{
		auto [x, y, z] = solve({ 0, a + 1 }, { 0, b + 1 }, { 0, c + 1 }, 1, 1, 1, { 0, 1, 2 });
		answer(x, y, z);
	}
	else
	{
		solveGreedy();
	}

	return 0;
}

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