Submission #676801

#	Time	Username	Problem	Language	Result	Execution time	Memory
676801		Cyanmond	Worm Worries (BOI18_worm)	C++17	47 / 100	536 ms	3916 KiB

worm

#include <bits/stdc++.h>

std::map<std::tuple<int, int, int>, int> memo;
int W;

int query(int x, int y = 0, int z = 0) {
    if (std::min({x, y, z}) < 0 or std::max({x, y, z}) >= W) {
        return 0;
    }
    if (memo.find({x, y, z}) != memo.end()) {
        return memo[{x, y, z}];
    }
    std::cout << '?' << ' ' << x + 1 << ' ' << y + 1 << ' ' << z + 1 << std::endl;
    int res;
    std::cin >> res;
    memo[{x, y, z}] = res;
    return res;
}

int finish(int x, int y = 0, int z = 0) {
    std::cout << '!' << ' ' << x + 1 << ' ' << y + 1 << ' ' << z + 1 << std::endl;
    std::exit(0);
}

void solve1() {
    int l = 0, r = W;
    while (r - l > 1) {
        auto mid = (l + r) / 2;
        const int lm_val = query(mid - 1), rm_val = query(mid);
        if (lm_val > rm_val) {
            r = mid;
        } else {
            l = mid;
        }
    }
    finish(l);
}

void solve2() {
    int xl = 0, xr = W, yl = 0, yr = W;
    while (std::max(xr - xl, yr - yl) > 1) {
        if (yr - yl > 1) {
            const auto ym = (yl + yr) / 2;
            int ma = -1, ma_id = -1;
            for (int i = xl; i < xr; ++i) {
                const int v = query(i, ym);
                if (v > ma) {
                    ma = v;
                    ma_id = i;
                }
            }
            const int v2 = query(ma_id, ym - 1);
            if (v2 > ma) {
                yr = ym;
            } else {
                yl = ym;
            }
        }

        if (xr - xl > 1) {
            const auto xm = (xl + xr) / 2;
            int ma = -1, ma_id = -1;
            for (int i = yl; i < yr; ++i) {
                const int v = query(xm, i);
                if (v > ma) {
                    ma = v;
                    ma_id = i;
                }
            }
            const int v2 = query(xm - 1, ma_id);
            if (v2 > ma) {
                xr = xm;
            } else {
                xl = xm;
            }
        }
    }
    finish(xl, yl);
}

constexpr std::array<std::tuple<int, int, int>, 6> dxyz = {{{0, 0, 1}, {0, 0, -1},
                                                        {0, 1, 0}, {0, -1, 0},
                                                        {1, 0, 0}, {-1, 0, 0}}};

void solve3(int Q) {
    int best = -1;
    int x = 0, y = 0, z = 0;
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());
    std::uniform_int_distribution dist(0, W);
    for (int i = 0; i < Q / 6; ++i) {
        --Q;
        const int nx = dist(engine), ny = dist(engine), nz = dist(engine);
        const int v = query(nx, ny, nz);
        if (v > best) {
            best = v;
            x = nx, y = ny, z = nz;
        }
    }

    while (Q > 0) {
        for (const auto &[ax, ay, az] : dxyz) {
            if (Q == 0) {
                break;
            }
            --Q;
            const auto nx = x + ax, ny = y + ay, nz = z + az;
            if (std::min({nx, ny, nz}) < 0 or std::max({nx, ny, nz}) >= W) {
                continue;
            }
            const int v = query(nx, ny, nz);
            if (v > best) {
                best = v;
                x = nx, y = ny, z = nz;
                break;
            }
        }
    }

    finish(x, y, z);
}

int main() {
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(nullptr);

    int N, M, K, Q;
    std::cin >> N >> M >> K >> Q;
    W = N;
    if (M == 1) {
        solve1();
    } else if (K == 1) {
        solve2();
    } else {
        solve3(Q);
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23