Submission #1259698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259698		patgra	Worm Worries (BOI18_worm)	C++20	10 / 100	232 ms	500448 KiB

worm

#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 = 1;
#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;
}

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) {
            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;
        }
        pair<int, int> mx = {0, 0};
        rep(i, l, r + 1) mx = max(mx, {query(i, 0, 0), i});
        guess(mx.second, 0, 0);
        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:51:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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