This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
mt19937 rd(20030101);
int n, m, k, q;
map<tuple<int, int, int>, int> height;
int genInt(int left, int right)
{
return left + abs(int(rd())) % (right - left + 1);
}
int ask(int x, int y, int z)
{
if (height.find(make_tuple(x, y, z)) != height.end())
{
return height[make_tuple(x, y, z)];
}
cout << "? " << x << ' ' << y << ' ' << z << endl;
int result;
cin >> result;
height[make_tuple(x, y, z)] = result;
return result;
}
void answer(int x, int y, int z)
{
cout << "! " << x << ' ' << y << ' ' << z << endl;
}
void subtask1()
{
double phi = (1 + sqrt(5)) / 2;
int left = 0, right = n + 1;
int mid = left + int((right - left - 1) / phi) + 1;
int val = ask(mid, 1, 1);
while (right - left > 2)
{
if (mid - left > right - mid)
{
int mid_ = left + int((mid - left - 1) / phi) + 1;
int val_ = ask(mid_, 1, 1);
if (val < val_)
{
right = mid;
mid = mid_;
val = val_;
}
else
{
left = mid_;
}
}
else
{
int mid_ = right - int((right - mid - 1) / phi) - 1;
int val_ = ask(mid_, 1, 1);
if (val < val_)
{
left = mid;
mid = mid_;
val = val_;
}
else
{
right = mid_;
}
}
}
answer(mid, 1, 1);
}
void solve(int i1, int j1, int i2, int j2, int i3, int j3, int a3, int flip)
{
int i, j, j_, a_;
i = (i1 + i2) / 2;
j_ = a_ = -1;
for (j = j1; j <= j2; j++)
{
int a = !flip ? ask(i, j, 1) : ask(j, i, 1);
if (a_ < a)
a_ = a, j_ = j;
}
if (a_ < a3)
{
if (i3 < i)
solve(j1, i1, j2, i - 1, j3, i3, a3, flip ^ 1);
else
solve(j1, i + 1, j2, i2, j3, i3, a3, flip ^ 1);
}
else if (i > i1 && a_ < (!flip ? ask(i - 1, j_, 1) : ask(j_, i - 1, 1)))
solve(j1, i1, j2, i - 1, j_, i, a_, flip ^ 1);
else if (i < i2 && a_ < (!flip ? ask(i + 1, j_, 1) : ask(j_, i + 1, 1)))
solve(j1, i + 1, j2, i2, j_, i, a_, flip ^ 1);
else if (!flip)
answer(i, j_, 1);
else
answer(j_, i, 1);
}
void subtask2()
{
solve(1, 1, n, m, -1, -1, -1, 0);
}
const int dx[6] = {1, -1, 0, 0, 0, 0};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const int dz[6] = {0, 0, 0, 0, 1, -1};
bool check(int x, int y, int z)
{
return (x > 0 && x <= n && y > 0 && y <= m && z > 0 && z <= k);
}
void subtask3()
{
int x, y, z, a = -1;
for (int i = 1; i <= q / 2; i++)
{
int nx = genInt(1, n), ny = genInt(1, m), nz = genInt(1, k);
int na = ask(nx, ny, nz);
if (a < na)
{
a = na;
x = nx;
y = ny;
z = nz;
}
}
while (true)
{
bool flag = false;
for (int i = 0; i < 6; i++)
{
int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i];
if (check(nx, ny, nz))
{
int na = ask(nx, ny, nz);
if (a < na)
{
a = na;
x = nx;
y = ny;
z = nz;
flag = true;
break;
}
}
}
if (!flag)
{
break;
}
}
answer(x, y, z);
}
int main()
{
cin >> n >> m >> k >> q;
if (m == 1 && k == 1)
{
subtask1();
}
else if (k == 1)
{
subtask2();
}
else
{
subtask3();
}
return 0;
}
Compilation message (stderr)
worm.cpp: In function 'void subtask3()':
worm.cpp:159:11: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
159 | answer(x, y, z);
| ~~~~~~^~~~~~~~~
worm.cpp:159:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:159:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |