oj.uz

Submission #825375

# Submission time Handle Problem Language Result Execution time Memory
825375 2023-08-14T18:59:12 Z QwertyPi Worm Worries (BOI18_worm) C++14
81 / 100
 864 ms 7336 KB 
#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 <= K)) 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 < 1500; 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 332 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 372 KB Output is correct
4 Correct 9 ms 404 KB Output is correct
5 Correct 7 ms 372 KB Output is correct
6 Correct 14 ms 356 KB Output is correct
7 Correct 15 ms 352 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 352 KB Output is correct
2 Correct 9 ms 308 KB Output is correct
3 Correct 8 ms 352 KB Output is correct
4 Correct 12 ms 352 KB Output is correct
5 Correct 14 ms 380 KB Output is correct
6 Correct 13 ms 364 KB Output is correct
7 Correct 10 ms 368 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Correct 10 ms 356 KB Output is correct
10 Correct 24 ms 480 KB Output is correct
11 Correct 29 ms 372 KB Output is correct
12 Correct 11 ms 372 KB Output is correct
13 Correct 11 ms 384 KB Output is correct
14 Correct 12 ms 344 KB Output is correct
15 Correct 11 ms 368 KB Output is correct
16 Correct 26 ms 352 KB Output is correct
17 Correct 11 ms 396 KB Output is correct
18 Incorrect 20 ms 488 KB too many queries. input: ? 103 238 1
19 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 6232 KB Output is correct
2 Correct 662 ms 6236 KB Output is correct
3 Correct 649 ms 6208 KB Output is correct
4 Correct 620 ms 6208 KB Output is correct
5 Correct 642 ms 6180 KB Output is correct
6 Correct 762 ms 6248 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 6544 KB Output is correct
2 Correct 744 ms 6524 KB Output is correct
3 Correct 670 ms 6520 KB Output is correct
4 Correct 718 ms 7336 KB Output is correct
5 Correct 752 ms 6476 KB Output is correct
6 Correct 629 ms 6636 KB Output is correct
7 Correct 818 ms 6496 KB Output is correct
8 Correct 604 ms 6572 KB Output is correct
9 Correct 651 ms 6820 KB Output is correct
10 Correct 787 ms 6804 KB Output is correct
11 Correct 753 ms 6552 KB Output is correct