Submission #696194

# Submission time Handle Problem Language Result Execution time Memory
696194 2023-02-05T19:33:40 Z bdl Worm Worries (BOI18_worm) C++17
100 / 100
790 ms 5176 KB
#include <array>
#include <iostream>
#include <cmath>
#include <random>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
  
struct hm_hash {
  const uint64_t C = (long long) (4e18 * acos(0)) | 71;
  
  uint64_t operator()(uint64_t x) const {
    return __builtin_bswap64(x * C);
  }
};
  
template<typename K, typename V>
using hash_map = __gnu_pbds::gp_hash_table<K, V, hm_hash>;

template<typename K>
using hash_set = hash_map<K, __gnu_pbds::null_type>;

#define ar array

const int NMK = 1.25e6;

int n, m, k, q;
hash_map<int, int> f;

int query(int x, int y, int z) {
  if (x < 0 || x >= n || y < 0 || y >= m || z < 0 || z >= k)
    return 0;
  int &v = f[(x * m + y) * k + z];
  if (v > 0)
    return v;
  q--;
  cout << "? " << x + 1 << ' ' << y + 1 << ' ' << z + 1 << endl;
  cin >> v;
  return v;
}

void answer(int x, int y, int z) {
  cout << "! " << x + 1 << ' ' << y + 1 << ' ' << z + 1 << endl;
  exit(0);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k >> q;
  if (m == 1 && k == 1) {
    int low = -1, hi = -1, x = 1, y = 1;
    while (low + y < n) {
      x += y;
      swap(x, y);
    }
    hi = low + y;
    while (x > 1) {
      y -= x;
      if (query(low + y, 0, 0) > query(hi - y, 0, 0))
        hi -= y;
      else
        low += y;
      swap(x, y);
    }
    answer(low + 1, 0, 0);
  } else if (k == 1) {
    int x1 = 0, x2 = n - 1, y1 = 0, y2 = m - 1;
    ar<int, 2> b = {-1, -1};
    while (x1 != x2 || y1 != y2) {
      if (x1 != x2) {
        int m = (x1 + x2) / 2;
        for (int i = y1; i <= y2; i++)
          if (query(m, i, 0) > query(b[0], b[1], 0))
            b = {m, i};
        if (b[0] < m)
          x2 = m - 1;
        else if (b[0] > m)
          x1 = m + 1;
        else if (query(m - 1, b[1], 0) > query(m, b[1], 0))
          x2 = m - 1;
        else if (query(m + 1, b[1], 0) > query(m, b[1], 0))
          x1 = m + 1;
        else
          answer(m, b[1], 0);
      }
      if (y1 != y2) {
        int m = (y1 + y2) / 2;
        for (int i = x1; i <= x2; i++)
          if (query(i, m, 0) > query(b[0], b[1], 0))
            b = {i, m};
        if (b[1] < m)
          y2 = m - 1;
        else if (b[1] > m)
          y1 = m + 1;
        else if (query(b[0], m - 1, 0) > query(b[0], m, 0))
          y2 = m - 1;
        else if (query(b[0], m + 1, 0) > query(b[0], m, 0))
          y1 = m + 1;
        else
          answer(b[0], m, 0);
      }
    }
    answer(x1, y1, 0);
  } else {
    int q_ = q;
    mt19937 rng(1234);
    int x = -1, y = -1, z = -1;
    while (q > q_ / 2) {
      int x_ = rng() % n, y_ = rng() % m, z_ = rng() % k;
      if (query(x_, y_, z_) > query(x, y, z))
        x = x_, y = y_, z = z_;
    }
    auto move = [&](int x_, int y_, int z_) -> bool {
      if (q > 0 && query(x_, y_, z_) > query(x, y, z)) {
        x = x_, y = y_, z = z_;
        return 1;
      }
      return 0;
    };
    while (q > 0)
      if (!(move(x + 1, y, z) || move(x - 1, y, z) || move(x, y + 1, z) || move(x, y - 1, z) || move(x, y, z + 1) || move(x, y, z - 1)))
        answer(x, y, z);
    answer(x, y, z);
  }
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 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
# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 0 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 0 ms 208 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 5 ms 312 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 464 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 8 ms 336 KB Output is correct
2 Correct 23 ms 400 KB Output is correct
3 Correct 8 ms 336 KB Output is correct
4 Correct 27 ms 396 KB Output is correct
5 Correct 26 ms 396 KB Output is correct
6 Correct 19 ms 520 KB Output is correct
7 Correct 19 ms 480 KB Output is correct
8 Correct 23 ms 504 KB Output is correct
9 Correct 22 ms 392 KB Output is correct
10 Correct 20 ms 464 KB Output is correct
11 Correct 28 ms 468 KB Output is correct
12 Correct 17 ms 484 KB Output is correct
13 Correct 21 ms 488 KB Output is correct
14 Correct 13 ms 456 KB Output is correct
15 Correct 28 ms 488 KB Output is correct
16 Correct 28 ms 456 KB Output is correct
17 Correct 22 ms 488 KB Output is correct
18 Correct 25 ms 456 KB Output is correct
19 Correct 29 ms 488 KB Output is correct
20 Correct 12 ms 344 KB Output is correct
21 Correct 21 ms 392 KB Output is correct
22 Correct 21 ms 404 KB Output is correct
23 Correct 18 ms 488 KB Output is correct
24 Correct 26 ms 456 KB Output is correct
25 Correct 22 ms 408 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 451 ms 2740 KB Output is correct
2 Correct 407 ms 2756 KB Output is correct
3 Correct 431 ms 2748 KB Output is correct
4 Correct 424 ms 2752 KB Output is correct
5 Correct 410 ms 2748 KB Output is correct
6 Correct 433 ms 2748 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 566 ms 5092 KB Output is correct
2 Correct 656 ms 5052 KB Output is correct
3 Correct 621 ms 5048 KB Output is correct
4 Correct 549 ms 5048 KB Output is correct
5 Correct 608 ms 5128 KB Output is correct
6 Correct 702 ms 5052 KB Output is correct
7 Correct 626 ms 5048 KB Output is correct
8 Correct 699 ms 5172 KB Output is correct
9 Correct 581 ms 5052 KB Output is correct
10 Correct 662 ms 5176 KB Output is correct
11 Correct 790 ms 5040 KB Output is correct