Submission #1261762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261762		patgra	Worm Worries (BOI18_worm)	C++20	100 / 100	491 ms	500452 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 = 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, ogq;

int query(int x, int y, int z) {
    if(x < 0 || x >= N || y < 0 || y >= M || z < 0 || z >= K) return -1;
    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);
    ogq = 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(Q == 35) {
        int l = 0, r = N - 1;
        int m1 = -1, m2 = -1;
        int vm1 = -1, vm2 = -1;
        double ratio = 0.38197;
        while(r - l + 1 > 3) {
            if(m1 < l || m1 > r) {
                m1 = (int)ceil(ratio * (r - l + 1)) + l;
                if(m1 == m2) m1--;
                if(m1 < l) m1 += 2;
                vm1 = query(m1, 0, 0);
            }
            if(m2 < l || m2 > r) {
                m2 = r - (int)ceil(ratio * (r - l + 1));
                if(m2 == m1) m2++;
                if(m2 > r) m2 -= 2;
                vm2 = query(m2, 0, 0);
            }
            if(m1 > m2) swap(m1, m2), swap(vm1, vm2);
            if(vm1 > vm2) {
                r = m2;
                m2 = m1;
                vm2 = vm1;
                m1 = -1;
                vm1 = -1;
            }
            else {
                l = m1;
                m1 = m2;
                vm1 = vm2;
                m2 = -1;
                vm2 = -1;
            }
        }
        if(r - l == 0) guess(l, 0, 0);
        if(r - l == 1) {
            if(query(l, 0, 0) < query(r, 0, 0)) guess(r, 0, 0);
            else if(query(l, 0, 0) > query(r, 0, 0)) guess(l, 0, 0);
            else if(l == 0) guess(l, 0, 0);
            else if(r == N - 1) guess(r, 0, 0);
            else if(query(l, 0, 0) >= query(l - 1, 0, 0)) guess(l, 0, 0);
            else guess(r, 0, 0);
        }
        if(r - l == 2) {
            if(query(l, 0, 0) < query(l + 1, 0, 0) && query(r, 0, 0) < query(l + 1, 0, 0)) guess(l + 1, 0, 0);
            else if(query(l, 0, 0) >= query(l + 1, 0, 0)) {
                if(l == 0 || query(l - 1, 0, 0) < query(l, 0, 0)) guess(l, 0, 0);
                else guess(r, 0, 0);
            }
            else {
                if(query(r, 0, 0) > query(l + 1, 0, 0)) guess(r, 0, 0);
                else guess(l + 1, 0, 0);
            }
        }
        return 0;
    }

    if(Q == 3500) {
        int l1 = 0, r1 = N, l2 = 0, r2 = M;
        pair<int, pair<int, int>> mxx = {-1, {-1, -1}};
        while(r1 - l1 > 3 || r2 - l2 > 3) {
            DC << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << eol;
            if(r1 - l1 > r2 - l2) {
                int m = (r1 + l1) / 2;
                pair<int, int> mx = {-1, -1};
                rep(i, l2, r2) mx = max(mx, {query(m, i, 0), i});
                if(mx.first < mxx.first) {
                    if(m < mxx.second.first) l1 = m + 1;
                    else r1 = m;
                    continue;
                }
                mxx = max(mxx, {mx.first, {m, mx.second}});
                int l = query(m - 1, mx.second, 0), r = query(m + 1, mx.second, 0);
                if(l < mx.first && r < mx.first) guess(m, mx.second, 0);
                if(l > r) r1 = m + 1;
                else l1 = m;
            }
            else {
                int m = (r2 + l2) / 2;
                pair<int, int> mx = {-1, -1};
                rep(i, l1, r1) mx = max(mx, {query(i, m, 0), i});
                if(mx.first < mxx.first) {
                    if(m < mxx.second.second) l2 = m + 1;
                    else r2 = m;
                    continue;
                }
                mxx = max(mxx, {mx.first, {mx.second, m}});
                int l = query(mx.second, m - 1, 0), r = query(mx.second, m + 1, 0);
                if(l < mx.first && r < mx.first) guess(mx.second, m, 0);
                if(l > r) r2 = m + 1;
                else l2 = m;
            }
        }
        DC << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << eol;
        rep(i, l1, r1 + 1) rep(j, l2, r2 + 1) if(tryit(i, j, 0)) guess(i, j, 0);
        return 1;
    }

    mt19937 rnd(2137 * N + Q);
    array<int, 4> mx = {{-1, 0, 0, 0}};
    while(Q * 2 > ogq) {
        int x = rnd() % N, y = rnd() % M, z = rnd() % K;
        mx = max(mx, {{query(x, y, z), x, y, z}});
        if(ogq - Q == N * M * K) break;
    }
    int x = mx[1], y = mx[2], z = mx[3];
    while(Q) {
        mx = max(mx, {{query(x + 1, y, z), x + 1, y, z}});
        if(!Q) break;
        mx = max(mx, {{query(x - 1, y, z), x - 1, y, z}});
        if(!Q) break;
        mx = max(mx, {{query(x, y + 1, z), x, y + 1, z}});
        if(!Q) break;
        mx = max(mx, {{query(x, y - 1, z), x, y - 1, z}});
        if(!Q) break;
        mx = max(mx, {{query(x, y, z + 1), x, y, z + 1}});
        if(!Q) break;
        mx = max(mx, {{query(x, y, z - 1), x, y, z - 1}});
        if(mx[0] == query(x, y, z)) break;
        x = mx[1], y = mx[2], z = mx[3];
    }
    guess(x, y, z);
}

Compilation message (stderr)

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

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