Submission #397416

#	Time	Username	Problem	Language	Result	Execution time	Memory
397416		KoD	Worm Worries (BOI18_worm)	C++17	58 / 100	842 ms	1048580 KiB

worm

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

int N, M, K, Q;
std::map<std::tuple<int, int, int>, int> memo;

int query(const int i, const int j, const int k) {
    std::tuple<int, int, int> tup(i, j, k);
    const auto itr = memo.find(tup);
    if (itr != memo.end()) {
        return itr -> second;
    }
    std::cout << "? " << i << ' ' << j << ' ' << k << std::endl;
    int ret;
    std::cin >> ret;
    assert(ret != -1);
    memo.emplace(std::move(tup), ret);
    return ret;
}

void answer(const int i, const int j, const int k) {
    std::cout << "! " << i << ' ' << j << ' ' << k << std::endl;
    std::exit(EXIT_SUCCESS);
}

template <class Select>
int fib_search(const int N, const Select& less) {
    Vec<int> fib(2, 1);
    while (fib.back() < N + 1) {
        const auto tmp = fib[fib.size() - 1] + fib[fib.size() - 2];
        fib.push_back(tmp);
    }
    int l = 0, r = N + 1, k = (int) fib.size() - 1;
    while (r - l > 2) {
        k -= 1;
        const auto m1 = r - fib[k];
        const auto m2 = l + fib[k];
        if (less(m1, m2)) {
            l = m1;
        }
        else {
            r = m2;
        }
    }
    return l + 1;
}

std::random_device dev;
std::default_random_engine gen(dev() ^ std::clock());

int main() {
    std::cin >> N >> M >> K >> Q;
    if (M == 1 and K == 1) {
        const auto ans = fib_search(N, [&](const int i, const int j) {
            if (j > N) return false;
            return query(i, 1, 1) <= query(j, 1, 1); 
        });
        answer(ans, 1, 1);
    }
    else if (K == 1) {
        const auto find_max = [&](const int i) {
            int ret = 1;
            for (int j = 2; j <= M; ++j) {
                if (query(i, ret, 1) < query(i, j, 1)) {
                    ret = j;
                }
            }
            return ret;
        };
        const auto ans = fib_search(N, [&](const int i, const int j) {
            if (j > N) return false;
            const auto x = find_max(i);
            const auto y = find_max(j);
            return query(i, x, 1) <= query(j, y, 1);
        });
        answer(ans, find_max(ans), 1);
    }
    else {
        Vec<std::tuple<int, int, int>> pts;
        pts.reserve(N * M * K);
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= M; ++j) {
                for (int k = 1; k <= K; ++k) {
                    pts.emplace_back(i, j, k);
                }
            }
        }
        std::shuffle(pts.begin(), pts.end(), gen);
        auto [i, j, k] = pts.front();
        for (int n = 1; n < Q / 2; ++n) {
            const auto [a, b, c] = pts[n];
            if (query(i, j, k) < query(a, b, c)) {
                i = a;
                j = b;
                k = c;
            }
        }
        while (true) {
            Vec<std::tuple<int, int, int, int>> around;
            const auto add = [&](const int a, const int b, const int c) {
                if (1 <= a and a <= N and 1 <= b and b <= M and 1 <= c and c <= K) {
                    around.emplace_back(query(a, b, c), a, b, c);
                }                
            };
            add(i - 1, j, k);
            add(i + 1, j, k);
            add(i, j - 1, k);
            add(i, j + 1, k);
            add(i, j, k - 1);
            add(i, j, k + 1);
            std::sort(around.begin(), around.end());
            auto [t, a, b, c] = around.back();
            if (t <= query(i, j, k)) {
                answer(i, j, k);
            }
            i = a;
            j = b;
            k = c;
        }
    }
    return 0;
}

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