Submission #403992

#	Time	Username	Problem	Language	Result	Execution time	Memory
403992		rama_pang	Worm Worries (BOI18_worm)	C++17	100 / 100	753 ms	456 KiB

worm

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

int N, M, K, Q;

int Query(int x, int y, int z) {
  if (x <= 0 || x > N || y <= 0 || y > M || z <= 0 || z > K) {
    return 0;
  }
  printf("? %d %d %d\n", x, y, z);
  fflush(stdout);
  assert(Q > 0);
  Q -= 1;
  int ans = -1;
  (void) scanf("%d", &ans);
  if (ans == -1) exit(0);
  return ans;
}

__attribute__((noreturn))
void Guess(int x, int y, int z) {
  printf("! %d %d %d\n", x, y, z);
  exit(0);
}

void Solve1D() { // golden section search
  static double PHI = (1.0 + sqrt(5)) / 2.0;
  auto Mean = [&](int l, int r) {
    return l + (r - l + 1) / PHI;
  };
  function<int(int, int, int, int)> Search = [&](int l, int r, int x, int fx) {
    if (l == r) return x;
    int y = Mean(l, r);
    if (x - l > r - x) y = l + r - y;
    if (x == y) y += 1;
    int fy = Query(y, 1, 1);
    if (x > y) swap(x, y), swap(fx, fy);
    if (fx > fy) {
      return Search(l, y - 1, x, fx);
    } else {
      return Search(x + 1, r, y, fy);
    }
  };
  return Guess(Search(1, N, Mean(1, N), Query(Mean(1, N), 1, 1)), 1, 1);
}

void Solve2D() {
  int cx = -1, cy = -1, cv = -1;
  function<pair<int, int>(int, int, int, int)> Solve = [&](int l, int r, int d, int u) {
    if (l == r && d == u) return make_pair(l, d);
    if (r - l > u - d) {
      int m = (l + r) / 2;
      vector<int> vals;
      for (int i = d; i <= u; i++) {
        vals.emplace_back(Query(m, i, 1));
      }
      int mx = max_element(begin(vals), end(vals)) - begin(vals);
      if (vals[mx] >= cv) {
        cx = cy = cv = -1;
        int lft = Query(m - 1, mx + d, 1);
        int rgt = Query(m + 1, mx + d, 1);
        if (vals[mx] >= lft && vals[mx] >= rgt) {
          return make_pair(m, mx + d);
        }
        if (lft > rgt) {
          cx = m - 1, cy = mx + d, cv = lft;
          return Solve(l, m - 1, d, u);
        } else {
          cx = m + 1, cy = mx + d, cv = rgt;
          return Solve(m + 1, r, d, u);
        }
      } else {
        if (cx < m) {
          return Solve(l, m - 1, d, u);
        } else {
          return Solve(m + 1, r, d, u);
        }
      }
    } else {
      int m = (u + d) / 2;
      vector<int> vals;
      for (int i = l; i <= r; i++) {
        vals.emplace_back(Query(i, m, 1));
      }
      int mx = max_element(begin(vals), end(vals)) - begin(vals);
      if (vals[mx] >= cv) {
        cx = cy = cv = -1;
        int lft = Query(mx + l, m - 1, 1);
        int rgt = Query(mx + l, m + 1, 1);
        if (vals[mx] >= lft && vals[mx] >= rgt) {
          return make_pair(mx + l, m);
        }
        if (lft > rgt) {
          cx = mx + l, cy = m - 1, cv = lft;
          return Solve(l, r, d, m - 1);
        } else {
          cx = mx + l, cy = m + 1, cv = rgt;
          return Solve(l, r, m + 1, u);
        }
      } else {
        if (cy < m) {
          return Solve(l, r, d, m - 1);
        } else {
          return Solve(l, r, m + 1, u);
        }
      }
    }
  };
  auto ans = Solve(1, N, 1, M);
  return Guess(ans.first, ans.second, 1);
}

void Solve3D() {
  auto RandomInt = [](int n) {
    static mt19937 rnd(123456789);
    return rnd() % n + 1;
  };

  int x = -1, y = -1, z = -1, v = -1;
  for (int i = 0; i * 2 < Q; i++) {
    int nx = RandomInt(N);
    int ny = RandomInt(M);
    int nz = RandomInt(K);
    int nv = Query(nx, ny, nz);
    if (v < nv) {
      x = nx;
      y = ny;
      z = nz;
      v = nv;
    }
  }
  while (true) {
    vector<int> around;
    for (int i = -1; i <= 1; i++) {
      for (int j = -1; j <= 1; j++) {
        for (int k = -1; k <= 1; k++) {
          if (abs(i) + abs(j) + abs(k) == 1) {
            around.emplace_back(Query(x + i, y + j, z + k));
          }
        }
      }
    }
    int mx = *max_element(begin(around), end(around));
    if (mx <= v) {
      Guess(x, y, z);
    }
    for (int i = -1, ptr = 0; i <= 1; i++) {
      for (int j = -1; j <= 1; j++) {
        for (int k = -1; k <= 1; k++) {
          if (ptr < (int) around.size() && abs(i) + abs(j) + abs(k) == 1 && around[ptr] == mx) {
            x += i;
            y += j;
            z += k;
            v = mx;
            ptr = around.size();
          }
          if (abs(i) + abs(j) + abs(k) == 1) {
            ptr += 1;
          }
        }
      }
    }
  }
}

int main() {
  (void) scanf("%d %d %d %d", &N, &M, &K, &Q);
  if (M == 1 && K == 1) {
    Solve1D();
  } else if (K == 1) {
    Solve2D();
  } else {
    Solve3D();
  }
  return 0;
}

Compilation message (stderr)

worm.cpp: In function 'int Query(int, int, int)':
worm.cpp:15:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   (void) scanf("%d", &ans);
      |          ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:167:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   (void) scanf("%d %d %d %d", &N, &M, &K, &Q);
      |          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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