Submission #825366

#	Time	Username	Problem	Language	Result	Execution time	Memory
825366		QwertyPi	Worm Worries (BOI18_worm)	C++14	32 / 100	1 ms	208 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);

#ifdef LOCAL
	random_device rd;
	mt19937 rng(rd());
	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);
	} 
}

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);
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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