| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 550973 | thuanqvbn03 | Worm Worries (BOI18_worm) | C++17 | 0 ms | 0 KiB |
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(29042003);
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 resuft;
cin >> resuft;
height[make_tuple(x, y, z)] = resuft;
return resulf;
}
void answer(int x, int y, int z)
{
cout << "? " << x << ' ' << y << ' ' << z << endl;
}
void subtask1()
{
double phi = (1 + sqrt(5)) / 2;
int left = 1, right = n;
int mid = left + (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, 1);
if (val < val_)
{
right = mid;
mid = mid_;
val = val_;
}
else
{
left = mid_;
}
}
else
{
int mid_ = right - int((right - mid - 1) / phi);
int val_ = ask(mid_, 1, 1);
if (val < val_)
{
left = mid;
mid = mid_;
val = _val;
}
else
{
right = mid_;
}
}
}
answer(mid_);
}
void solve(int i1, int j1, int i2, int j2, int i3, int j3, int a3, int flip)
{
int i = (i1 + i2) / 2;
int j_ = -1, a_ = -1;
for (int 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, i3, j3, i3, a3, flip ^ 1);
}
}
else if (i > i1 && a_ < (!flip ? query(i - 1, j_, 1) : query(j_, i - 1, 1)))
{
solve2(j1, i1, j2, i - 1, j_, i, a_, flip ^ 1);
}
else if (i < i2 && a_ < (!flip ? query(i + 1, j_, 1) : query(j_, i + 1, 1)))
[solve2(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);
}
void subtask3()
{
int h, i, j, l, a, i_, j_, l_, a_;
i_ = j_ = l_ = a_ = -1;
for (h = 0; h < q / 2; h++)
{
i = randInt(1, n) % n, j = randInt(1, m), l = rand(1, k), a = query(i, j, k);
if (a_ < a)
{
a_ = a, i_ = i, j_ = j, l_ = l;
}
}
i = i_, j = j_, l = l_, a = a_;
while (1)
{
if (i > 1 && a < (a_ = query(i - 1, j, l)))
{
a = a_, i--;
}
else if (i < n && a < (a_ = query(i + 1, j, l)))
{
a = a_, i++;
}
else if (j > 1 && a < (a_ = query(i, j - 1, l)))
{
a = a_, j--;
}
else if (j < m && a < (a_ = query(i, j + 1, l)))
{
a = a_, j++;
}
else if (l > 1 && a < (a_ = query(i, j, l - 1)))
{
a = a_, l--;
}
else if (l < k && a < (a_ = query(i, j, l + 1)))
{
a = a_, l++;
}
else
{
break;
}
}
answer(i, j, l);
}
int main()
{
cin >> n >> m >> k >> q;
if (m == 1 && k == 1)
{
subtask1();
}
else if (k == 1)
{
subtask2();
}
else
{
subtask3();
}
return 0;
}