oj.uz

Submission #403992

# Submission time Handle Problem Language Result Execution time Memory
403992 2021-05-13T16:23:56 Z rama_pang Worm Worries (BOI18_worm) C++17
100 / 100
 753 ms 456 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 200 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 5 ms 200 KB Output is correct
2 Correct 5 ms 200 KB Output is correct
3 Correct 4 ms 200 KB Output is correct
4 Correct 8 ms 200 KB Output is correct
5 Correct 7 ms 328 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 6 ms 292 KB Output is correct
2 Correct 28 ms 300 KB Output is correct
3 Correct 14 ms 200 KB Output is correct
4 Correct 31 ms 296 KB Output is correct
5 Correct 29 ms 456 KB Output is correct
6 Correct 41 ms 300 KB Output is correct
7 Correct 27 ms 296 KB Output is correct
8 Correct 31 ms 200 KB Output is correct
9 Correct 40 ms 284 KB Output is correct
10 Correct 21 ms 304 KB Output is correct
11 Correct 29 ms 296 KB Output is correct
12 Correct 35 ms 280 KB Output is correct
13 Correct 20 ms 320 KB Output is correct
14 Correct 34 ms 292 KB Output is correct
15 Correct 28 ms 200 KB Output is correct
16 Correct 39 ms 200 KB Output is correct
17 Correct 33 ms 200 KB Output is correct
18 Correct 24 ms 296 KB Output is correct
19 Correct 39 ms 284 KB Output is correct
20 Correct 16 ms 200 KB Output is correct
21 Correct 25 ms 300 KB Output is correct
22 Correct 31 ms 200 KB Output is correct
23 Correct 41 ms 320 KB Output is correct
24 Correct 33 ms 288 KB Output is correct
25 Correct 31 ms 200 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 200 KB Output is correct
2 Correct 383 ms 200 KB Output is correct
3 Correct 382 ms 200 KB Output is correct
4 Correct 242 ms 200 KB Output is correct
5 Correct 414 ms 200 KB Output is correct
6 Correct 402 ms 292 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 200 KB Output is correct
2 Correct 502 ms 200 KB Output is correct
3 Correct 557 ms 200 KB Output is correct
4 Correct 549 ms 200 KB Output is correct
5 Correct 576 ms 200 KB Output is correct
6 Correct 426 ms 200 KB Output is correct
7 Correct 591 ms 200 KB Output is correct
8 Correct 750 ms 264 KB Output is correct
9 Correct 753 ms 272 KB Output is correct
10 Correct 593 ms 264 KB Output is correct
11 Correct 375 ms 268 KB Output is correct