Submission #397434

#	Time	Username	Problem	Language	Result	Execution time	Memory
397434		KoD	Worm Worries (BOI18_worm)	C++17	100 / 100	1069 ms	6264 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 best, best_x, best_y, best_z;

int query(const int i, const int j = 1, const int k = 1) {
    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;
    if (best < ret) {
        best = ret;
        best_x = i;
        best_y = j;
        best_z = k;
    }
    memo.emplace(std::move(tup), ret);
    return ret;
}

__attribute__((noreturn))
void answer(const int i, const int j = 1, const int k = 1) {
    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 rand_int(const int low, const int high) {
    return std::uniform_int_distribution<int>(low, high)(gen);
}

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) <= query(j); 
        });
        answer(ans);
    }
    else if (K == 1) {
        int L = 1, R = M, U = 1, D = N;
        while (L < R or U < D) {
            if (R - L > D - U) {
                const auto m = (L + R) / 2;
                for (int i = U; i <= D; ++i) query(i, m);
                if (best_y == m and m < M) query(best_x, m + 1);
                if (best_y == m and m > 1) query(best_x, m - 1);
                if (best_y == m) answer(best_x, best_y);
                if (best_y < m) R = m - 1;
                else L = m + 1;
            }
            else {
                const auto m = (U + D) / 2;
                for (int i = L; i <= R; ++i) query(m, i);
                if (best_x == m and m < N) query(m + 1, best_y);
                if (best_x == m and m > 1) query(m - 1, best_y);
                if (best_x == m) answer(best_x, best_y);
                if (best_x < m) D = m - 1;
                else U = m + 1;
            }
        }
        answer(U, L);
    }
    else {
        Vec<std::tuple<int, int, int>> pts;
        for (int i = 0; i < Q / 2; ++i) {
            pts.emplace_back(rand_int(1, N), rand_int(1, M), rand_int(1, K));
        }
        for (int n = 0; n < Q / 2; ++n) {
            const auto [a, b, c] = pts[n];
            query(a, b, c);
        }
        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) {
                query(a, b, c);
            }                
        };
        while (true) {
            int last = best;
            add(best_x - 1, best_y, best_z);
            add(best_x + 1, best_y, best_z);
            add(best_x, best_y - 1, best_z);
            add(best_x, best_y + 1, best_z);
            add(best_x, best_y, best_z - 1);
            add(best_x, best_y, best_z + 1);
            if (best == last) break;
        }
        answer(best_x, best_y, best_z);
    }
    return 0;
}

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