Submission #676847

#	Time	Username	Problem	Language	Result	Execution time	Memory
676847		Cyanmond	Worm Worries (BOI18_worm)	C++17	100 / 100	790 ms	6084 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;
    if (res == -1) {
        std::exit(0);
    }
    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() {
    // fib search
    int l = -1, r = W;
    int x = 1, y = 1;
    while (l + y < r) {
        x += y;
        std::swap(x, y);
    }
    r = l + y;
    while (x > 1) {
        y -= x;
        if (query(l + y) < query(r - y)) {
            l += y;
        } else {
            r -= y;
        }
        std::swap(x, y);
    }
    finish(l + x);
}

void solve2() {
    int xl = 0, xr = W - 1, yl = 0, yr = W - 1;
    std::pair<int, int> best = {-1, -1};
    while (xl != xr or yl != yr) {
        if (yl != yr) {
            const auto ym = (yl + yr) / 2;
            for (int i = xl; i <= xr; ++i) {
                const int v = query(i, ym);
                if (v > query(best.first, best.second)) {
                    best.first = i;
                    best.second = ym;
                }
            }
            if (best.second != ym) {
                if (best.second < ym) {
                    yr = ym - 1;
                } else {
                    yl = ym + 1;
                }
            } else {
                const int v2_a = query(best.first, best.second - 1), v2_b = query(best.first, best.second + 1);
                if (v2_a > query(best.first, best.second)) {
                    yr = ym - 1;
                } else if (v2_b > query(best.first, best.second)) {
                    yl = ym + 1;
                } else {
                    finish(best.first, best.second);
                }
            }
        }

        if (xl != xr) {
            const auto xm = (xl + xr) / 2;
            for (int i = yl; i <= yr; ++i) {
                const int v = query(xm, i);
                if (v > query(best.first, best.second)) {
                    best.first = xm;
                    best.second = i;
                }
            }
            if (best.first != xm) {
                if (best.first < xm) {
                    xr = xm - 1;
                } else {
                    xl = xm + 1;
                }
            } else {
                const int v2_a = query(best.first - 1, best.second), v2_b = query(best.first + 1, best.second);
                if (v2_a > query(best.first, best.second)) {
                    xr = xm - 1;
                } else if (v2_b > query(best.first, best.second)) {
                    xl = xm + 1;
                } else {
                    finish(best.first, best.second);
                }
            }
        }
    }
    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() {
    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: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23