# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
124774 |
2019-07-03T23:43:12 Z |
tutis |
Worm Worries (BOI18_worm) |
C++17 |
|
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);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |