제출 #180882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
180882		gs13068	Worm Worries (BOI18_worm)	C++17	100 / 100	696 ms	3284 KiB

worm

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23