Submission #124774

#	Time	Username	Problem	Language	Result	Execution time	Memory
124774		tutis	Worm Worries (BOI18_worm)	C++17	100 / 100	1006 ms	5496 KiB

worm

/*input
1000 1000 1 4000
8 6 2 1 5 6 9 4 5 2 3 5 4 8 1 11 1 1 156 64 456 56 4321 321 56156 564 564 6 1 11 1 1 1 11 1 1 15 1 51 156 5156  11 1 1 11 1 1 14 1 1 11 1 11 1 1 1 1 11 1 1 1 15 5 5 3 3 3 3 6 6 61 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 5 5 6 6 68 8 84 4 456
*/
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
int N, M, K, Q;
map<tuple<int, int, int>, int>MAPPPAS;
map<int, int>G;
int timer = 2;
int mxxx = -1;
int x3 = 1;
int y3 = 1;
int query(int x, int y, int z)
{
	if (x <= 0 || x > N || y <= 0 || y > M || z <= 0 || z > K)
		return 0;
	if (MAPPPAS.count(make_tuple(x, y, z)))
		return MAPPPAS[make_tuple(x, y, z)];
	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
	int ans = -1;
	ans = timer;
	timer += 5;
	if (rand() % 5 == 0)
		ans -= 18;
	(void)scanf("%d", &ans);
	if (ans >= mxxx)
	{
		mxxx = ans;
		x3 = x;
		y3 = y;
	}
	if (ans == -1) exit(0);
	G[x] = ans;
	return MAPPPAS[make_tuple(x, y, z)] = ans;
}

void guess(int x, int y, int z)
{
	if (query(x + 1, y, z) > query(x, y, z))
		return guess(x + 1, y, z);
	if (query(x - 1, y, z) > query(x, y, z))
		return guess(x - 1, y, z);
	if (query(x, y + 1, z) > query(x, y, z))
		return guess(x, y + 1, z);
	if (query(x, y - 1, z) > query(x, y, z))
		return guess(x, y - 1, z);
	if (query(x, y, z + 1) > query(x, y, z))
		return guess(x, y, z + 1);
	if (query(x, y, z - 1) > query(x, y, z))
		return guess(x, y, z - 1);
	printf("! %d %d %d\n", x, y, z);
	cerr << MAPPPAS.size() << endl;
	exit(0);
}
void spresk1()
{
	int l = 1;
	int r = N;
	while (r - l + 1 >= 5)
	{
		int m1 = l + (r - l) * 0.37;
		int m2 = max(m1 + 1, r - (m1 - l));
		auto it = G.upper_bound(l);
		if (it != G.end() && it->first < r)
		{
			int m = it->first;
			if (m >= (l + r) / 2)
			{
				m2 = m;
			}
			else
			{
				m1 = m;
			}
		}
		//cout << l << " " << m1 << " " << m2 << " " << r << endl;
		if (query(m1, 1, 1) >= query(m2, 1, 1))
			r = m2 - 1;
		else
			l = m1 + 1;
	}
	guess(l, 1, 1);
}
void spresk2(int x1, int x2, int y1, int y2)
{
	if (x2 - x1 >= y2 - y1)
	{
		int x = (x1 + x2) / 2;
		pair<int, int>mx = { -1, -1};
		for (int y = y1; y <= y2; y++)
			mx = max(mx, {query(x, y, 1), y});
		int y = mx.second;
		query(x + 1, y, 1);
		query(x - 1, y, 1);
		query(x, y - 1, 1);
		query(x, y + 1, 1);
		if (x3 > x)
			return spresk2(x + 1, x2, y1, y2);
		if (x3 < x)
			return spresk2(x1, x - 1, y1, y2);
		guess(x3, y3, 1);
	}
	else
	{
		int y = (y1 + y2) / 2;
		pair<int, int>mx = { -1, -1};
		for (int x = x1; x <= x2; x++)
			mx = max(mx, {query(x, y, 1), x});
		int x = mx.second;
		query(x + 1, y, 1);
		query(x - 1, y, 1);
		query(x, y - 1, 1);
		query(x, y + 1, 1);
		if (y3 > y)
			return spresk2(x1, x2, y + 1, y2);
		if (y3 < y)
			return spresk2(x1, x2, y1, y - 1);
		guess(x3, y3, 1);
	}
}
void Random()
{
	int mx = -1;
	int x = 1, y = 1, z = 1;
	for (int gal = 0; gal < Q / 2; gal++)
	{
		int a = (rand() % N) + 1;
		int b = (rand() % M) + 1;
		int c = (rand() % K) + 1;
		if (query(a, b, c) >= query(x, y, z))
		{
			mx = query(a, b, c);
			x = a;
			y = b;
			z = c;
		}
	}
	guess(x, y, z);
}
int main()
{
	srand(clock());
	(void)scanf("%d %d %d %d", &N, &M, &K, &Q);
	if (M == 1 && K == 1)
		spresk1();
	if (K == 1)
		spresk2(1, N, 1, M);
	Random();
}

Compilation message (stderr)

worm.cpp: In function 'void Random()':
worm.cpp:127:6: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
  int mx = -1;
      ^~
worm.cpp: In function 'int query(int, int, int)':
worm.cpp:29:2: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  (void)scanf("%d", &ans);
  ^~~~~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:147:2: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  (void)scanf("%d %d %d %d", &N, &M, &K, &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