oj.uz

Submission #624167

# Submission time Handle Problem Language Result Execution time Memory
624167 2022-08-07T11:19:09 Z KoD Worm Worries (BOI18_worm) C++17
100 / 100
 841 ms 5340 KB 
#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() {
    int x = 0, y = 0, f = 0;
    const auto add = [&](const int i, const int j) {
        const int g = query(i, j);
        if (f < g) {
            x = i;
            y = j;
            f = g;
        }
    };
    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;
            for (int k = j0; k <= j1; ++k) {
                add(i, k);
            }
            add(x - 1, y);            
            add(x + 1, y);
            if (x < i) {
                dfs(i0, i - 1, j0, j1);
            } else if (x > i) {
                dfs(i + 1, i1, j0, j1);
            } else {
                answer(x, y);
            }
        } else {
            const int j = (j0 + j1) / 2;
            for (int k = i0; k <= i1; ++k) {
                add(k, j);
            }
            add(x, y - 1);
            add(x, y + 1);
            if (y < j) {
                dfs(i0, i1, j0, j - 1);
            } else if (y > j) {
                dfs(i0, i1, j + 1, j1);
            } else {
                answer(x, y);
            }
        }
    })(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.0 / 10.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 7 ms 360 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 6 ms 208 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 25 ms 460 KB Output is correct
3 Correct 10 ms 336 KB Output is correct
4 Correct 33 ms 428 KB Output is correct
5 Correct 33 ms 348 KB Output is correct
6 Correct 33 ms 444 KB Output is correct
7 Correct 25 ms 396 KB Output is correct
8 Correct 25 ms 460 KB Output is correct
9 Correct 39 ms 396 KB Output is correct
10 Correct 14 ms 404 KB Output is correct
11 Correct 32 ms 460 KB Output is correct
12 Correct 27 ms 460 KB Output is correct
13 Correct 26 ms 584 KB Output is correct
14 Correct 31 ms 648 KB Output is correct
15 Correct 16 ms 416 KB Output is correct
16 Correct 33 ms 456 KB Output is correct
17 Correct 26 ms 388 KB Output is correct
18 Correct 29 ms 456 KB Output is correct
19 Correct 27 ms 448 KB Output is correct
20 Correct 17 ms 400 KB Output is correct
21 Correct 29 ms 408 KB Output is correct
22 Correct 26 ms 524 KB Output is correct
23 Correct 13 ms 428 KB Output is correct
24 Correct 15 ms 436 KB Output is correct
25 Correct 25 ms 340 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 3236 KB Output is correct
2 Correct 333 ms 3328 KB Output is correct
3 Correct 445 ms 3288 KB Output is correct
4 Correct 525 ms 3328 KB Output is correct
5 Correct 492 ms 3244 KB Output is correct
6 Correct 309 ms 3216 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 4932 KB Output is correct
2 Correct 713 ms 4968 KB Output is correct
3 Correct 544 ms 4900 KB Output is correct
4 Correct 811 ms 4960 KB Output is correct
5 Correct 613 ms 5236 KB Output is correct
6 Correct 619 ms 5184 KB Output is correct
7 Correct 744 ms 5112 KB Output is correct
8 Correct 769 ms 4992 KB Output is correct
9 Correct 677 ms 5244 KB Output is correct
10 Correct 841 ms 5276 KB Output is correct
11 Correct 544 ms 5340 KB Output is correct