Submission #397400

#	Time	Username	Problem	Language	Result	Execution time	Memory
397400		KoD	Worm Worries (BOI18_worm)	C++17	32 / 100	6 ms	4168 KiB

worm

#include <bits/stdc++.h>

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

int main() {
    int N, M, K, Q;
    std::cin >> N >> M >> K >> Q;

    const auto query = [&](const int i, const int j, const int k) {
        std::cout << "? " << i << ' ' << j << ' ' << k << std::endl;
        int ret;
        std::cin >> ret;
        assert(ret != -1);
        return ret;
    };

    const auto answer = [&](const int i, const int j, const int k) {
        std::cout << "! " << i << ' ' << j << ' ' << k << std::endl;
        std::exit(EXIT_SUCCESS);
    };

    if (M == 1 and K == 1) {
        Vec<int> fib(2);
        fib[0] = fib[1] = 1;
        while (fib.back() < N + 1) {
            const auto tmp = fib[fib.size() - 1] + fib[fib.size() - 2];
            fib.push_back(tmp);
        }
        Vec<int> memo(N + 1);
        const auto ask = [&](const int i) {
            if (i > N) {
                return N - i;
            }
            if (memo[i] == 0) {
                memo[i] = query(i, 1, 1);
            }
            return memo[i];
        };
        int l = 0, r = N + 1, k = (int) fib.size() - 1;
        while (r - l > 2) {
            const auto m1 = r - fib[k - 1];
            const auto m2 = l + fib[k - 1];
            if (ask(m1) >= ask(m2)) {
                r = m2;
            }
            else {
                l = m1;
            }
            k -= 1;
        }
        answer(l + 1, 1, 1);
    }
    return 0;
}

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