| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 442599 | abc864197532 | Worm Worries (BOI18_worm) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cerr << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 200000;
map <array<int, 3>, int> m1;
int n, m, k, q, dx[6] = {1, -1, 0, 0, 0, 0}, dy[6] = {0, 0, 1, -1, 0, 0}, dz[6] = {0, 0, 0, 0, 1, -1};
int ask(int i, int j, int kk) {
if (i < 0 || i >= n || j < 0 || j >= m || kk < 0 || kk >= k) return 0;
if (!m1.count({i, j, kk})) {
assert(q);
cout << "? " << i + 1 << ' ' << j + 1 << ' ' << kk + 1 << endl;
cin >> m1[{i, j, kk}];
q--;
}
return m1[{i, j, kk}];
}
void chk(int i, int j, int kk) {
bool is = true;
for (int ii = 0; ii < 6; ++ii) {
is &= ask(i, j, kk) >= ask(i + dx[ii], j + dy[ii], kk + dz[ii]);
}
if (is) {
cout << "! " << i + 1 << ' ' << j + 1 << ' ' << kk + 1 << endl;
exit(0);
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k >> q;
if (m == 1 && k == 1) {
// task 1 & 2
int l = 0, r = n;
while (r - l > 2) {
int mid = l + r >> 1;
if (ask(mid, 0, 0) > ask(mid + 1, 0, 0)) r = mid + 1;
else l = mid + 1;
}
for (int i = l; i < r; ++i) chk(i, 0, 0);
} else if (k == 1) {
// task 3 & 4
int l1 = 0, r1 = n, l2 = 0, r2 = m;
while (r1 - l1 > 5) {
{
int mid = l1 + r1 >> 1;
int mx1 = 0, mx2 = 0;
for (int j = l2; j < r2; ++j) {
mx1 = max(mx1, ask(mid - 1, j, 0));
mx2 = max(mx2, ask(mid, j, 0));
}
if (mx1 > mx2) r1 = mid;
else l1 = mid;
}
{
int mid = l2 + r2 >> 1;
int mx1 = 0, mx2 = 0;
for (int j = l1; j < r1; ++j) {
mx1 = max(mx1, ask(j, mid - 1, 0));
mx2 = max(mx2, ask(j, mid, 0));
}
if (mx1 > mx2) r2 = mid;
else l2 = mid;
}
}
for (int i = l1; i < r1; ++i) {
for (int j = l2; j < r2; ++j) {
chk(i, j, 0);
}
}
assert(false);
} else {
// task 5 & 6
int l1 = 0, r1 = n;
for (int _ = 0; _ < 5; ++_) {
int mid = l1 + r1 >> 1;
int mx1 = 0, mx2 = 0;
for (int i = 0; i < m ++i) for (int j = 0; j < k; ++j) {
mx1 = max(mx1, ask(mid - 1, i, j));
mx2 = max(mx2, ask(mid, i, j));
}
if (mx1 > mx2) r1 = mid;
else l1 = mid;
}
for (int i = l1; i < r1; ++i) for (int j = 0; j < m; ++j) for (int kk = 0; kk < k; ++kk) {
chk(i, j, k);
}
assert(false);
}
}