제출 #1345599

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

// 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;
}

template <typename F>
int bin_search_axis(int c, int m, F &&check) {
    if (m > 1 && check(c) >= max(check(c - 1), check(c + 1))) {
        return c;
    }
    
    int l = 1, r = m;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid) < check(mid + 1)) l = mid + 1;
        else r = mid;
    }

    return l;
}

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

    int x = (n + 1) / 2, y = (m + 1) / 2, z = (k + 1) / 2;
    // bool changed;
    // do {
    //     int px = x, py = y, pz = z;
    //     x = bin_search_axis(x, n, [&](int x) { return humidity(x, y, z); });
    //     y = bin_search_axis(y, m, [&](int y) { return humidity(x, y, z); });
    //     z = bin_search_axis(z, k, [&](int z) { return humidity(x, y, z); });
    //     changed = px != x || py != y || pz != z;
    // } while (changed);

    bool changed;
    int amount_x = n / 2, amount_y = m / 2, amount_z = k / 2;
    do {
        changed = false;
        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 (ma > humidity(x, y, z)) {
            changed = true;
            switch (dir) {
                case 0: x += amount_x; break;
                case 1: x -= amount_x; break;
                case 2: y += amount_y; break;
                case 3: y -= amount_y; break;
                case 4: z += amount_z; break;
                case 5: z -= amount_z; break;
            }
            amount_x /= 2, amount_y /= 2, amount_z /= 2;
        }
    } 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...