Submission #624165

#	Time	Username	Problem	Language	Result	Execution time	Memory
624165		KoD	Worm Worries (BOI18_worm)	C++17	69 / 100	801 ms	5336 KiB

worm

#include <bits/stdc++.h>

using std::vector;
using std::pair;
using std::tuple;
using std::array;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int N, M, K, Q;

bool inside(const int x, const int y, const int z) {
    return 1 <= x and x <= N and 1 <= y and y <= M and 1 <= z and z <= K;
}

int query(const int x = 1, const int y = 1, const int z = 1) {
    static std::map<array<int, 3>, int> memo = {};
    if (inside(x, y, z)) {
        auto& ret = memo[{x, y, z}];
        if (ret == 0) {
            std::cout << "? " << x << " " << y << " " << z << std::endl;
            std::cin >> ret;
        }
        return ret;
    } else {
        return 0;
    }
}

void answer(const int x = 1, const int y = 1, const int z = 1) {
    assert(inside(x, y, z));
    std::cout << "! " << x << " " << y << " " << z << std::endl;
    std::exit(EXIT_SUCCESS);
}

void solve_1D() {
    int l = 0, r = N + 1;
    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);
    }
    answer(l + x);
}

void solve_2D() {
    fixed([&](auto&& dfs, const int i0, const int i1, const int j0, const int j1) -> void {
        if (i1 - i0 > j1 - j0) {
            const int i = (i0 + i1) / 2;
            int j = 0, fj = 0;
            for (int k = j0; k <= j1; ++k) {
                const int fk = query(i, k);
                if (fj < fk) {
                    j = k;
                    fj = fk;
                }
            }
            if (fj < query(i - 1, j)) {
                dfs(i0, i - 1, j0, j1);
            } else if (fj < query(i + 1, j)) {
                dfs(i + 1, i1, j0, j1);
            } else {
                assert(fj == query(i, j));
                answer(i, j);
            }
        } else {
            const int j = (j0 + j1) / 2;
            int i = 0, fi = 0;
            for (int k = i0; k <= i1; ++k) {
                const int fk = query(k, j);
                if (fi < fk) {
                    i = k;
                    fi = fk;
                }
            }
            if (i0 < i and i < i1) {
                assert(fi >= query(i - 1, j));
                assert(fi >= query(i + 1, j));
            }
            if (fi < query(i, j - 1)) {
                dfs(i0, i1, j0, j - 1);
            } else if (fi < query(i, j + 1)) {
                dfs(i0, i1, j + 1, j1);
            } else {
                assert(fi == query(i, j));
                answer(i, j);
            }
        }
    })(1, N, 1, M);
}

void solve_3D() {
    std::default_random_engine gen(0xABCDEF);
    std::uniform_int_distribution<int> gx(1, N), gy(1, M), gz(1, K);
    int i = 0, j = 0, k = 0, f = 0;
    for (int q = 0; q < Q / 2; ++q) {
        const int x = gx(gen);
        const int y = gy(gen);
        const int z = gz(gen);
        const int g = query(x, y, z);
        if (f < g) {
            i = x;
            j = y;
            k = z;
            f = g;
        }
    }
    while (true) {
        if ([&] {
            for (int x = i - 1; x <= i + 1; ++x) {
                for (int y = j - 1; y <= j + 1; ++y) {
                    for (int z = k - 1; z <= k + 1; ++z) {
                        if (std::abs(i - x) + std::abs(j - y) + std::abs(k - z) != 1) {
                            continue;
                        }
                        const int g = query(x, y, z);
                        if (f < g) {
                            i = x;
                            j = y;
                            k = z;
                            f = g;
                            return false;
                        }
                    }
                }
            }
            return true;
        }()) {
            answer(i, j, k);
        }
    }
}

int main() {
    std::cin >> N >> M >> K >> Q;
    if (M == 1 and K == 1) {
        solve_1D();
    } else if (K == 1) {
        solve_2D();
    } else {
        solve_3D();
    }
}

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