제출 #1345720

#제출 시각아이디문제언어결과실행 시간메모리
1345720BlockOGWorm Worries (BOI18_worm)C++20
37 / 100
225 ms5892 KiB
#include <bits/stdc++.h>
#include <cstddef>

// mrrrowwww meeowwwww :3
// go play vivid/stasis! !! !!! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = []{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    return 0;
}();

int n, m, k;

map<pair<int, pair<int, int>>, int> cache;
int humidity(int x, int y, int z) {
    if (!cache.count({ x, { y, z } }) && x >= 1 && y >= 1 && z >= 1 && x <= n && y <= m && z <= k) {
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        cin >> cache[{ x, { y, z } }];
    }
    return cache[{ x, { y, z } }];
}

void answer(int x, int y, int z) {
    cout << "! " << x << ' ' << y << ' ' << z << endl;
}

const double inv_phi = (sqrt(5.0F) - 1) / 2;
const double rinv_phi = 1 - inv_phi;
mt19937 rng(time(NULL));

template <typename F>
int search_axis(int m, F &&check, int s=1) {
    int l = s, r = m;
    int a = round(l * inv_phi + r * rinv_phi), b = round(l * rinv_phi + r * inv_phi);
    while (l + 1 < r - 1) {
        if (check(a) < check(max(a + 1, b))) l = a + 1, a = round(l * inv_phi + r * rinv_phi);
        else r = b - 1, b = round(l * rinv_phi + r * inv_phi);
    }

    if (check(l) <= check(l + 1) && check(l + 1) >= check(l + 2))
        return l + 1;
    else if (check(l - 1) <= check(l) && check(l) >= check(l + 1))
        return l;
    return l + 2;
}

int main() {
    int q; cin >> n >> m >> k >> q;

    int x = 1, y = 1, z = 1;
    if (m == 1 && k == 1) {
        x = search_axis(n, [&](int x) { return humidity(x, y, z); });
    } else if (k == 1) {
        int lx = 1, rx = n;
        int ly = 1, ry = m;
        while (lx < rx || ly < ry) {
            if (lx < rx) {
                int mid = (lx + rx) / 2;
                int by = search_axis(ry, [&](int y) { return humidity(mid, y, z); }, ly);
                if (humidity(mid - 1, by, z) <= humidity(mid, by, z) && humidity(mid, by, z) >= humidity(mid + 1, by, z)) {
                    x = mid, y = by;
                    break;
                } else if (humidity(mid - 1, by, z) > humidity(mid + 1, by, z))
                    rx = mid - 1;
                else
                    lx = mid + 1;
            }
            
            if (ly < ry) {
                int mid = (ly + ry) / 2;
                int bx = search_axis(rx, [&](int x) { return humidity(x, mid, z); }, lx);
                if (humidity(bx, mid - 1, z) <= humidity(bx, mid, z) && humidity(bx, mid, z) >= humidity(bx, mid + 1, z)) {
                    x = bx, y = mid;
                    break;
                } else if (humidity(bx, mid - 1, z) > humidity(bx, mid + 1, z))
                    ry = mid - 1;
                else
                    ly = mid + 1;
            }
        }
    } else {
        int ma = 0, bx, by, bz;
        fo(_, 0, q / 2) {
            int x = 1 + rng() % n, y = 1 + rng() % m, z = 1 + rng() % k;
            if (humidity(x, y, z) > ma)
                ma = humidity(x, y, z), bx = x, by = y, bz = z;
        }
        x = bx, y = by, z = bz;

        bool changed;
        do {
            int ma = humidity(x, y, z), dir;
            if (humidity(x + 1, y, z) > ma) ma = humidity(x + 1, y, z), dir = 0;
            if (humidity(x - 1, y, z) > ma) ma = humidity(x - 1, y, z), dir = 1;
            if (humidity(x, y + 1, z) > ma) ma = humidity(x, y + 1, z), dir = 2;
            if (humidity(x, y - 1, z) > ma) ma = humidity(x, y - 1, z), dir = 3;
            if (humidity(x, y, z + 1) > ma) ma = humidity(x, y, z + 1), dir = 4;
            if (humidity(x, y, z - 1) > ma) ma = humidity(x, y, z - 1), dir = 5;
            if (changed = ma > humidity(x, y, z)) {
                switch (dir) {
                    case 0: x++; break;
                    case 1: x--; break;
                    case 2: y++; break;
                    case 3: y--; break;
                    case 4: z++; break;
                    case 5: z--; break;
                }
            }
        } while (changed);
    }

    answer(x, y, z);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...