Submission #825372

#	Time	Username	Problem	Language	Result	Execution time	Memory
825372		QwertyPi	Worm Worries (BOI18_worm)	C++14	69 / 100	864 ms	7720 KiB

worm

#include <bits/stdc++.h>

using namespace std;

int N, M, K, Q;

#ifdef LOCAL

vector<vector<vector<int>>> a;

int get(int x, int y, int z){
	if(!(1 <= x && x <= N && 1 <= y && y <= M && 1 <= z && z <= Q)) return 0;
	return a[x - 1][y - 1][z - 1];
}

int query(int x, int y, int z) {
	assert(1 <= x && x <= N && 1 <= y && y <= M && 1 <= z && z <= Q);
	return get(x, y, z);
}

void guess(int x, int y, int z) {
	assert(1 <= x && x <= N && 1 <= y && y <= M && 1 <= z && z <= Q);
	bool ok = true;
	ok &= get(x, y, z) >= get(x - 1, y, z);
	ok &= get(x, y, z) >= get(x + 1, y, z);
	ok &= get(x, y, z) >= get(x, y - 1, z);
	ok &= get(x, y, z) >= get(x, y + 1, z);
	ok &= get(x, y, z) >= get(x, y, z - 1);
	ok &= get(x, y, z) >= get(x, y, z + 1);
	assert(ok); 
}

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

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

map<pair<pair<int, int>, int>, int> mp;
int s_query(int x, int y, int z){
	if(!(1 <= x && x <= N && 1 <= y && y <= M && 1 <= z && z <= Q)) return 0;
    if(mp.count({{x, y}, z})) return mp[{{x, y}, z}];
    return mp[{{x, y}, z}] = query(x, y, z);
}

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

#ifdef LOCAL
	a = vector<vector<vector<int>>>(N, vector<vector<int>>(M, vector<int>(K)));
	for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) for(int k = 0; k < K; k++)
		a[i][j][k] = (rng() % 100 + 100) % 100;
#endif
	if(M == 1 && K == 1){
        int l = 1, r = N;
		int m1 = (int) (l * 1.618 + r * 1.0) / 2.618, m2 = (int) (l * 1.0 + r * 1.618) / 2.618;
        int q1 = s_query(m1, 1, 1), q2 = s_query(m2, 1, 1);
        while(l + 3 < r){
            if(m1 == m2) break;
            if(q1 <= q2){
                l = m1 + 1, q1 = q2, m1 = m2;
                m2 = (int) (m1 * 1.0 + r * 0.618) / 1.618; q2 = s_query(m2, 1, 1);
            }else{
                r = m2 - 1, q2 = q1, m2 = m1;
                m1 = (int) (l * 0.618 + m2 * 1.0) / 1.618; q1 = s_query(m1, 1, 1);
            }
            // assert(max(s_query(m1, 1, 1), s_query(m2, 1, 1)) >= max(s_query(l - 1, 1, 1), s_query(r + 1, 1, 1)));
        }

        for(int i = l; i <= r; i++){
            if(s_query(i, 1, 1) >= max(s_query(i - 1, 1, 1), s_query(i + 1, 1, 1))){
                guess(i, 1, 1);
                return 0;
            }
        }
        assert(1 == 0);
	}else if(K == 1){
        int cur_best = -1, x, y, z;
        for(int q = 0; q < 2000; q++){
            int qx = rng() % N + 1, qy = rng() % M + 1, qz = rng() % K + 1;
            int sq = s_query(qx, qy, qz);
            if(sq > cur_best) cur_best = sq, x = qx, y = qy, z = qz;
        }
        while(true){
            if(s_query(x + 1, y, z) > s_query(x, y, z)){ x++; continue; }
            if(s_query(x - 1, y, z) > s_query(x, y, z)){ x--; continue; }
            if(s_query(x, y + 1, z) > s_query(x, y, z)){ y++; continue; }
            if(s_query(x, y - 1, z) > s_query(x, y, z)){ y--; continue; }
            if(s_query(x, y, z + 1) > s_query(x, y, z)){ z++; continue; }
            if(s_query(x, y, z - 1) > s_query(x, y, z)){ z--; continue; }
            guess(x, y, z);
            return 0;
        }

        assert(1 == 0);
    }

    int cur_best = -1, x, y, z;
    for(int q = 0; q < 100000; q++){
        int qx = rng() % N + 1, qy = rng() % M + 1, qz = rng() % K + 1;
        int sq = s_query(qx, qy, qz);
        if(sq > cur_best) cur_best = sq, x = qx, y = qy, z = qz;
    }
    while(true){
        if(s_query(x + 1, y, z) > s_query(x, y, z)){ x++; continue; }
        if(s_query(x - 1, y, z) > s_query(x, y, z)){ x--; continue; }
        if(s_query(x, y + 1, z) > s_query(x, y, z)){ y++; continue; }
        if(s_query(x, y - 1, z) > s_query(x, y, z)){ y--; continue; }
        if(s_query(x, y, z + 1) > s_query(x, y, z)){ z++; continue; }
        if(s_query(x, y, z - 1) > s_query(x, y, z)){ z--; continue; }
        guess(x, y, z);
        return 0;
    }
}

Compilation message (stderr)

worm.cpp: In function 'int query(int, int, int)':
worm.cpp:38:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  (void)scanf("%d", &ans);
      |        ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:58:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp:124:14: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |         guess(x, y, z);
      |         ~~~~~^~~~~~~~~
worm.cpp:124:14: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:124:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:104:18: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |             guess(x, y, z);
      |             ~~~~~^~~~~~~~~
worm.cpp:104:18: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:104:18: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

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