oj.uz

Submission #124774

# Submission time Handle Problem Language Result Execution time Memory
124774 2019-07-03T23:43:12 Z tutis Worm Worries (BOI18_worm) C++17
100 / 100
 1006 ms 5496 KB 
/*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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 320 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 5 ms 316 KB Output is correct
3 Correct 9 ms 376 KB Output is correct
4 Correct 9 ms 248 KB Output is correct
5 Correct 11 ms 248 KB Output is correct
6 Correct 6 ms 248 KB Output is correct
7 Correct 6 ms 420 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 464 KB Output is correct
2 Correct 31 ms 432 KB Output is correct
3 Correct 36 ms 552 KB Output is correct
4 Correct 38 ms 512 KB Output is correct
5 Correct 32 ms 520 KB Output is correct
6 Correct 24 ms 504 KB Output is correct
7 Correct 38 ms 452 KB Output is correct
8 Correct 19 ms 460 KB Output is correct
9 Correct 32 ms 504 KB Output is correct
10 Correct 38 ms 504 KB Output is correct
11 Correct 33 ms 696 KB Output is correct
12 Correct 33 ms 456 KB Output is correct
13 Correct 31 ms 504 KB Output is correct
14 Correct 32 ms 520 KB Output is correct
15 Correct 35 ms 508 KB Output is correct
16 Correct 22 ms 448 KB Output is correct
17 Correct 41 ms 504 KB Output is correct
18 Correct 39 ms 508 KB Output is correct
19 Correct 23 ms 444 KB Output is correct
20 Correct 24 ms 376 KB Output is correct
21 Correct 36 ms 504 KB Output is correct
22 Correct 35 ms 460 KB Output is correct
23 Correct 19 ms 532 KB Output is correct
24 Correct 32 ms 548 KB Output is correct
25 Correct 32 ms 504 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 3448 KB Output is correct
2 Correct 517 ms 3448 KB Output is correct
3 Correct 472 ms 3388 KB Output is correct
4 Correct 511 ms 3448 KB Output is correct
5 Correct 602 ms 3320 KB Output is correct
6 Correct 556 ms 3352 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 5040 KB Output is correct
2 Correct 889 ms 5032 KB Output is correct
3 Correct 937 ms 5136 KB Output is correct
4 Correct 955 ms 5120 KB Output is correct
5 Correct 1006 ms 5496 KB Output is correct
6 Correct 942 ms 5276 KB Output is correct
7 Correct 913 ms 5292 KB Output is correct
8 Correct 733 ms 5180 KB Output is correct
9 Correct 792 ms 5176 KB Output is correct
10 Correct 899 ms 5112 KB Output is correct
11 Correct 963 ms 5496 KB Output is correct