Submission #451536

#	Time	Username	Problem	Language	Result	Execution time	Memory
451536		nonsensenonsense1	Worm Worries (BOI18_worm)	C++17	81 / 100	3067 ms	1252 KiB

worm

#include <cstdio>
#include <chrono>
#include <random>
#include <algorithm>

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

int n, m, k, q;

int query(int x, int y = 1, int z = 1) 
{
	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
	scanf("%d", &x);
	return x;
}

void task1() 
{
	int l = 1, r = n, x = -1, xval, y = -1, yval;
	while (l < r) {
		if (x == -1) {
			x = (34 * l + 21 * r) / 55;
			if (y != -1) x = std::min(x, y - 1);
			if (!x) {
				++x;
				++y;
				yval = query(y);
			}
			xval = query(x);
		}
		if (y == -1) {
			y = (21 * l + 34 * r - 1) / 55 + 1;
			if (x != -1) y = std::max(y, x + 1);
			if (y == n + 1) {
				--x;
				--y;
				xval = query(x);
			}
			yval = query(y);
		}
		if (xval > yval) {
			r = y - 1;
			y = x;
			yval = xval;
			x = -1;
		}
		else {
			l = x + 1;
			x = y;
			xval = yval;
			y = -1;
		}
	}
	printf("! %d 1 1\n", l);
}

bool u[1001][1001];

void modify(int &x, int &y, int &z, int ind) 
{
	if (!ind) --x;
	else if (ind == 1) ++x;
	else if (ind == 2) --y;
	else if (ind == 3) ++y;
	else if (ind == 4) --z;
	else ++z;
}

int go2(int x, int y, int ind) 
{
	int z;
	modify(x, y, z, ind);
	if (x < 1 || x > n || y < 1 || y > m || u[x][y]) return -1;
	if (!q) while (true);
	--q;
	u[x][y] = true;
	return query(x, y);
}

void task2() 
{
	int x, y, val = -1;
	for (int i = 0; i < q / 2; ++i) {
		int cx = rng() % n + 1, cy = rng() % m + 1, v = query(cx, cy);
		u[cx][cy] = 1;
		if (v > val) {
			val = v;
			x = cx;
			y = cy;
		}
	}
	q /= 2;
	int move[4], to;
	std::iota(move, move + 4, 0);
	do {
		std::shuffle(move, move + 4, rng);
		int v;
		for (to = 0; to < 4; ++to) if ((v = go2(x, y, to)) > val) {
			val = v;
			modify(x, y, v, to);
			break;
		}
	} while (to < 4);
	printf("! %d %d 1\n", x, y);
}

int go(int x, int y, int z, int ind) 
{
	modify(x, y, z, ind);
	if (x < 1 || x > n || y < 1 || y > m || z < 1 || z > k) return -1;
	return query(x, y, z);
}

void task3() 
{
	int x, y, z, val = -1;
	for (int i = 0; i < q / 2; ++i) {
		int cx = rng() % n + 1, cy = rng() % m + 1, cz = rng() % k + 1, v = query(cx, cy, cz);
		if (v > val) {
			val = v;
			x = cx;
			y = cy;
			z = cz;
		}
	}
	int move[6];
	std::iota(move, move + 6, 0);
	int to;
	do {
		std::shuffle(move, move + 6, rng);
		int v;
		for (to = 0; to < 6; ++to) if ((v = go(x, y, z, move[to])) > val) {
			modify(x, y, z, move[to]);
			val = v;
			break;
		}
	} while (to < 6);
	printf("! %d %d %d\n", x, y, z);
}

int main() 
{
	scanf("%d%d%d%d", &n, &m, &k, &q);
	if (k == 1) {
		if (m == 1) task1();
		else task2();
	}
	else task3();
	return 0;
}

Compilation message (stderr)

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d", &x);
      |  ~~~~~^~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d%d%d%d", &n, &m, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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