oj.uz

Submission #397434

# Submission time Handle Problem Language Result Execution time Memory
397434 2021-05-02T07:48:36 Z KoD Worm Worries (BOI18_worm) C++17
100 / 100
 1069 ms 6264 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 328 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 3 ms 200 KB Output is correct
4 Correct 6 ms 328 KB Output is correct
5 Correct 8 ms 200 KB Output is correct
6 Correct 3 ms 200 KB Output is correct
7 Correct 9 ms 200 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 316 KB Output is correct
2 Correct 33 ms 452 KB Output is correct
3 Correct 14 ms 328 KB Output is correct
4 Correct 41 ms 456 KB Output is correct
5 Correct 35 ms 448 KB Output is correct
6 Correct 36 ms 464 KB Output is correct
7 Correct 38 ms 464 KB Output is correct
8 Correct 39 ms 444 KB Output is correct
9 Correct 38 ms 348 KB Output is correct
10 Correct 43 ms 448 KB Output is correct
11 Correct 32 ms 448 KB Output is correct
12 Correct 29 ms 404 KB Output is correct
13 Correct 33 ms 360 KB Output is correct
14 Correct 31 ms 424 KB Output is correct
15 Correct 43 ms 500 KB Output is correct
16 Correct 24 ms 424 KB Output is correct
17 Correct 40 ms 368 KB Output is correct
18 Correct 45 ms 364 KB Output is correct
19 Correct 42 ms 448 KB Output is correct
20 Correct 25 ms 328 KB Output is correct
21 Correct 16 ms 428 KB Output is correct
22 Correct 23 ms 448 KB Output is correct
23 Correct 46 ms 556 KB Output is correct
24 Correct 18 ms 428 KB Output is correct
25 Correct 42 ms 356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 3936 KB Output is correct
2 Correct 503 ms 4008 KB Output is correct
3 Correct 572 ms 3916 KB Output is correct
4 Correct 579 ms 4064 KB Output is correct
5 Correct 516 ms 3864 KB Output is correct
6 Correct 453 ms 3948 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 5768 KB Output is correct
2 Correct 619 ms 6068 KB Output is correct
3 Correct 915 ms 5836 KB Output is correct
4 Correct 681 ms 5912 KB Output is correct
5 Correct 718 ms 6264 KB Output is correct
6 Correct 892 ms 5868 KB Output is correct
7 Correct 788 ms 6004 KB Output is correct
8 Correct 1069 ms 6004 KB Output is correct
9 Correct 1018 ms 6176 KB Output is correct
10 Correct 705 ms 5984 KB Output is correct
11 Correct 874 ms 6176 KB Output is correct