Submission #452133

#	Time	Username	Problem	Language	Result	Execution time	Memory
452133		nonsensenonsense1	Worm Worries (BOI18_worm)	C++17	100 / 100	954 ms	276 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) 
{
	if (x < 1 || x > n || y < 1 || y > m || z < 1 || z > k) return -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);
}

void task2() 
{
	int x1 = 1, y1 = 1, x2 = n, y2 = m, xx, yy, val = -1;
	while (true) {
		if (x2 - x1 < y2 - y1) {
			int m = y1 + y2 >> 1, mx = -1, pos, cur;
			for (int i = x1; i <= x2; ++i) if ((cur = query(i, m)) > mx) {
				mx = cur;
				pos = i;
			}
			if (val > mx) {
				if (yy < m) y2 = m - 1;
				else y1 = m + 1;
			}
			else {
				val = mx;
				int l = query(pos, m - 1), r = query(pos, m + 1);
				xx = pos;
				if (val < l) yy = y2 = m - 1;
				else if (val < r) yy = y1 = m + 1;
				else {
					printf("! %d %d 1\n", xx, m);
					return;
				}
			}
		}
		else {
			int m = x1 + x2 >> 1, mx = -1, pos, cur;
			for (int i = y1; i <= y2; ++i) if ((cur = query(m, i)) > mx) {
				mx = cur;
				pos = i;
			}
			if (val > mx) {
				if (xx < m) x2 = m - 1;
				else x1 = m + 1;
			}
			else {
				val = mx;
				int l = query(m - 1, pos), r = query(m + 1, pos);
				yy = pos;
				if (val < l) xx = x2 = m - 1;
				else if (val < r) xx = x1 = m + 1;
				else {
					printf("! %d %d 1\n", m, yy);
					return;
				}
			}
		}
	}
}

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 go(int x, int y, int z, int ind) 
{
	modify(x, y, z, ind);
	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 'void task2()':
worm.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |    int m = y1 + y2 >> 1, mx = -1, pos, cur;
      |            ~~~^~~~
worm.cpp:86:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |    int m = x1 + x2 >> 1, mx = -1, pos, cur;
      |            ~~~^~~~
worm.cpp: In function 'int query(int, int, int)':
worm.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d", &x);
      |  ~~~~~^~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  scanf("%d%d%d%d", &n, &m, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'void task1()':
worm.cpp:43:3: warning: 'yval' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   if (xval > yval) {
      |   ^~
worm.cpp: In function 'void task2()':
worm.cpp:70:5: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     if (yy < m) y2 = m - 1;
      |     ^~
worm.cpp:92:5: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |     if (xx < m) x2 = m - 1;
      |     ^~

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