Submission #1268706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268706		rtri	Worm Worries (BOI18_worm)	C++20	26 / 100	403 ms	428 KiB

worm

#include <bits/stdc++.h>
using namespace std;

const tuple<int, int, int> dirs[] = {{1, 0, 0},  {-1, 0, 0}, {0, 1, 0},
                                     {0, -1, 0}, {0, 0, 1},  {0, 0, -1}};
int n, m, k, q;

int ask(int x, int y, int z) {
  if (x < 0 || y < 0 || z < 0)
    return 0;
  if (n <= x || m <= y || k <= z)
    return 0;

  cout << "? " << x + 1 << " " << y + 1 << " " << z + 1 << endl;
  int ans;
  cin >> ans;
  return ans;
}

int main() {
  srand(time({}));

  cin >> n >> m >> k >> q;

  priority_queue<tuple<int, int, int, int>> pq;

  for (int i = 0; i < sqrt(q); i++) {
    int x = rand() % n, y = rand() % m, z = rand() % k;
    int val = ask(x, y, z);
    pq.push({val, x, y, z});
  }

  while (true) {
    auto [v, x, y, z] = pq.top();
    pq.pop();
    bool good = true;
    for (auto [xoff, yoff, zoff] : dirs) {
      int adj_v = ask(x + xoff, y + yoff, z + zoff);
      if (v < adj_v) {
        pq.push({adj_v, x + xoff, y + yoff, z + zoff});
        good = false;
        break;
      }
    }

    if (good) {
      cout << "! " << x + 1 << " " << y + 1 << " " << z + 1 << endl;
      return 0;
    }
  }

  return 0;
}

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