Submission #1259708

#TimeUsernameProblemLanguageResultExecution timeMemory
1259708patgraWorm Worries (BOI18_worm)C++20
10 / 100
225 ms500448 KiB
#include <bits/stdc++.h> #define rep(a,b,c) for(auto a = (b); a != (c); a++) #define repD(a,b,c) for(auto a = (b); a != (c); a--) #define repIn(a, b) for(auto& a : (b)) #define repIn2(a, b, c) for(auto& [a, b] : (c)) constexpr bool dbg = 0; #define DEBUG if constexpr(dbg) #define DC DEBUG std::cerr #define eol std::endl #define ll long long #define pb push_back #define ld long double using namespace std; constexpr bool readit = 0; vector<vector<vector<int>>> heights; int N, M, K, Q; int query(int x, int y, int z) { if(heights[x][y][z] != -1) return heights[x][y][z]; if(!Q) return -1; printf("? %d %d %d\n", x + 1, y + 1, z + 1); fflush(stdout); Q--; int ans = -1; (void)scanf("%d", &ans); if (ans == -1) exit(0); heights[x][y][z] = ans; return ans; } bool tryit(int x, int y, int z) { return (x == 0 || query(x, y, z) >= query(x - 1, y, z)) && (x == N - 1 || query(x, y, z) >= query(x + 1, y, z)) && (y == 0 || query(x, y, z) >= query(x, y - 1, z)) && (y == M - 1 || query(x, y, z) >= query(x, y + 1, z)) && (z == 0 || query(x, y, z) >= query(x, y, z - 1)) && (z == K - 1 || query(x, y, z) >= query(x, y, z + 1)); } void guess(int x, int y, int z) { x++, y++, z++; printf("! %d %d %d\n", x, y, z); x--, y--, z--; if constexpr(readit) assert((x == 0 || heights[x][y][z] >= heights[x - 1][y][z]) && (x == N - 1 || heights[x][y][z] >= heights[x + 1][y][z]) && (y == 0 || heights[x][y][z] >= heights[x][y - 1][z]) && (y == M - 1 || heights[x][y][z] >= heights[x][y + 1][z]) && (z == 0 || heights[x][y][z] >= heights[x][y][z - 1]) && (z == K - 1 || heights[x][y][z] >= heights[x][y][z + 1])); exit(0); } int main() { (void)scanf("%d %d %d %d", &N, &M, &K, &Q); heights.resize(N, vector<vector<int>>(M, vector<int>(K, -1))); if constexpr(readit) rep(i, 0, N) rep(j, 0, M) rep(k, 0, K) scanf("%d", &heights[i][j][k]); if(M == 1 && K == 1) { int l = 0, r = N - 1; while(r - l > 3) { DC << l << ' ' << r << eol; auto turd = max(1, (r - l + 1) / 3); auto ml = l + turd; auto mr = r - turd; auto mlh = query(ml, 0, 0), mrh = query(mr, 0, 0); if(mlh < mrh) l = ml; else r = mr; } DC << l << ' ' << r << eol; rep(i, l, r + 1) if(tryit(i, 0, 0)) guess(i, 0, 0); guess(-1, -1, -1); return 0; } int x = 0, y = 0, z = 0; ld lr = N * 3 / 2.0, alpha = 0.9; bool found = false; while(!found) { int nx = x, ny = y, nz = z; int dl = x == 0 ? 0 : max(0, query(x - 1, y, z) - query(x, y, z)); int dr = x == N - 1 ? 0 : max(0, query(x + 1, y, z) - query(x, y, z)); if(dl > dr) nx -= (int)ceil(lr); else if(dr > dl)nx += (int)ceil(lr); dl = y == 0 ? 0 : max(0, query(x, y - 1, z) - query(x, y, z)); dr = y == M - 1 ? 0 : max(0, query(x, y + 1, z) - query(x, y, z)); if(dl > dr) nx -= (int)ceil(lr); else if(dr > dl)nx += (int)ceil(lr); dl = z == 0 ? 0 : max(0, query(x, y, z - 1) - query(x, y, z)); dr = z == K - 1 ? 0 : max(0, query(x, y, z + 1) - query(x, y, z)); if(dl > dr) nx -= (int)ceil(lr); else if(dr > dl)nx += (int)ceil(lr); nx = min(max(0, nx), N - 1); ny = min(max(0, ny), M - 1); nz = min(max(0, nz), K - 1); if(x == nx && y == ny && z == nz) found = true; x = nx, y = ny, z = nz; lr *= alpha; } guess(x, y, z); }

Compilation message (stderr)

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:31:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         (void)scanf("%d", &ans);
      |               ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:60:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...