oj.uz

Submission #180882

# Submission time Handle Problem Language Result Execution time Memory
180882 2020-01-09T05:57:43 Z gs13068 Worm Worries (BOI18_worm) C++17
100 / 100
 696 ms 3284 KB 
#include <stdio.h>
#include <stdlib.h>
#include <map>

int __query(int x, int y, int z) {
	printf("? %d %d %d\n", x, y, z);
	fflush(stdout);
	int ans = -1;
  (void)scanf("%d", &ans);
	if (ans == -1) exit(0);
	return ans;
}

std::map<int, int> M;
int mw, mx, my, mz;
int query(int x, int y, int z) {
  int t = x - 1 | y - 1 << 10 | z - 1 << 20;
  if (M.find(t) == M.end()) {
    int w = __query(x, y, z);
    M[t] = w;
    if (w > mw) {
      mw = w;
      mx = x;
      my = y;
      mz = z;
    }
    return w;
  }
  return M[t];
}

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

const double p = 0.381966;

int px[6] = { 1, -1, 0, 0, 0, 0 };
int py[6] = { 0, 0, 1, -1, 0, 0 };
int pz[6] = { 0, 0, 0, 0, 1, -1 };

int main() {
	int N, M, K, Q;
	(void)scanf("%d %d %d %d", &N, &M, &K, &Q);

	// TODO do something smart
	if (M == 1) {
    int L = 1, R = N;
    int T = L * p + R * (1 - p) + .5;
    while (L < R) {
      if (T + T == L + R) T = L * (1 - p) + R * p + .236;
      int T2 = L + R - T;
      if (T > T2) {
        int T3 = T;
        T = T2;
        T2 = T3;
      }
      if (query(T, 1, 1) > query(T2, 1, 1)) R = T2 - 1;
      else {
        L = T + 1;
        T = T2;
      }
    }
    guess(L, 1, 1);
  }
  if (K == 1) {
    int i, m, T, L = 1, R = N, D = 1, U = M;
    while (L < R || D < U) {
      if (R - L > U - D) {
        m = L + R >> 1;
        for (i = D; i <= U; i++) query(m, i, 1);
        if (mx == m) query(m + 1, my, 1);
        if (mx > m) L = m + 1;
        else R = m;
      }
      else {
        m = D + U >> 1;
        for (i = L; i <= R; i++) query(i, m, 1);
        if (my == m) query(mx, m + 1, 1);
        if (my > m) D = m + 1;
        else U = m;
      }
    }
    guess(L, D, 1);
  }
  int i, x, y, z, w = -1;
  for (i = 0; i < Q / 5; i++) {
    int tx = rand() % N + 1;
    int ty = rand() % M + 1;
    int tz = rand() % K + 1;
    if (query(tx, ty, tz) > w) {
      w = query(tx, ty, tz);
      x = tx;
      y = ty;
      z = tz;
    }
  }
  do {
    for (i = 0; i < 6; i++) {
      int tx = x + px[i], ty = y + py[i], tz = z + pz[i];
      if (tx > 0 && tx <= N && ty > 0 && ty <= M && tz > 0 && tz <= K && query(tx, ty, tz) > query(x, y, z)) {
        x = tx;
        y = ty;
        z = tz;
        break;
      }
    }
  } while (i < 6);
  guess(x, y, z);
}

Compilation message

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:17:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   int t = x - 1 | y - 1 << 10 | z - 1 << 20;
                   ~~^~~
worm.cpp:17:13: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   int t = x - 1 | y - 1 << 10 | z - 1 << 20;
           ~~^~~
worm.cpp:17:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   int t = x - 1 | y - 1 << 10 | z - 1 << 20;
                                 ~~^~~
worm.cpp: In function 'int main()':
worm.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m = L + R >> 1;
             ~~^~~
worm.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         m = D + U >> 1;
             ~~^~~
worm.cpp:69:15: warning: unused variable 'T' [-Wunused-variable]
     int i, m, T, L = 1, R = N, D = 1, U = M;
               ^
worm.cpp: In function 'int __query(int, int, int)':
worm.cpp:9:3: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   (void)scanf("%d", &ans);
   ^~~~~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:46:2: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp:111:8: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   guess(x, y, z);
   ~~~~~^~~~~~~~~
worm.cpp:111:8: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:111:8: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 10.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 296 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 5 ms 388 KB Output is correct
4 Correct 5 ms 312 KB Output is correct
5 Correct 5 ms 316 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 10 ms 376 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 532 KB Output is correct
2 Correct 33 ms 424 KB Output is correct
3 Correct 29 ms 428 KB Output is correct
4 Correct 35 ms 504 KB Output is correct
5 Correct 19 ms 496 KB Output is correct
6 Correct 37 ms 544 KB Output is correct
7 Correct 31 ms 376 KB Output is correct
8 Correct 31 ms 504 KB Output is correct
9 Correct 37 ms 376 KB Output is correct
10 Correct 39 ms 416 KB Output is correct
11 Correct 33 ms 424 KB Output is correct
12 Correct 40 ms 424 KB Output is correct
13 Correct 42 ms 488 KB Output is correct
14 Correct 25 ms 504 KB Output is correct
15 Correct 38 ms 344 KB Output is correct
16 Correct 30 ms 404 KB Output is correct
17 Correct 32 ms 392 KB Output is correct
18 Correct 32 ms 376 KB Output is correct
19 Correct 31 ms 552 KB Output is correct
20 Correct 38 ms 424 KB Output is correct
21 Correct 33 ms 504 KB Output is correct
22 Correct 34 ms 552 KB Output is correct
23 Correct 24 ms 396 KB Output is correct
24 Correct 31 ms 376 KB Output is correct
25 Correct 17 ms 432 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1108 KB Output is correct
2 Correct 227 ms 1204 KB Output is correct
3 Correct 225 ms 1216 KB Output is correct
4 Correct 240 ms 1208 KB Output is correct
5 Correct 217 ms 1108 KB Output is correct
6 Correct 130 ms 1196 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 1704 KB Output is correct
2 Correct 270 ms 1688 KB Output is correct
3 Correct 233 ms 1744 KB Output is correct
4 Correct 399 ms 1980 KB Output is correct
5 Correct 395 ms 1852 KB Output is correct
6 Correct 353 ms 1856 KB Output is correct
7 Correct 470 ms 2204 KB Output is correct
8 Correct 466 ms 2604 KB Output is correct
9 Correct 423 ms 1832 KB Output is correct
10 Correct 696 ms 3284 KB Output is correct
11 Correct 559 ms 2692 KB Output is correct