oj.uz

Submission #825373

# Submission time Handle Problem Language Result Execution time Memory
825373 2023-08-14T18:57:05 Z QwertyPi Worm Worries (BOI18_worm) C++14
81 / 100
 894 ms 7764 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 < 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

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 0 ms 208 KB Output is correct
2 Correct 0 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 0 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 0 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 1 ms 208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 336 KB Output is correct
2 Correct 12 ms 400 KB Output is correct
3 Correct 16 ms 356 KB Output is correct
4 Correct 18 ms 376 KB Output is correct
5 Correct 15 ms 388 KB Output is correct
6 Correct 19 ms 320 KB Output is correct
7 Correct 12 ms 336 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 388 KB Output is correct
2 Correct 19 ms 488 KB Output is correct
3 Correct 13 ms 336 KB Output is correct
4 Correct 14 ms 412 KB Output is correct
5 Correct 30 ms 600 KB Output is correct
6 Correct 20 ms 384 KB Output is correct
7 Correct 23 ms 356 KB Output is correct
8 Correct 24 ms 464 KB Output is correct
9 Correct 14 ms 404 KB Output is correct
10 Correct 17 ms 512 KB Output is correct
11 Correct 19 ms 392 KB Output is correct
12 Correct 20 ms 356 KB Output is correct
13 Correct 22 ms 384 KB Output is correct
14 Correct 19 ms 348 KB Output is correct
15 Correct 16 ms 372 KB Output is correct
16 Correct 19 ms 372 KB Output is correct
17 Correct 23 ms 468 KB Output is correct
18 Correct 14 ms 416 KB Output is correct
19 Correct 20 ms 360 KB Output is correct
20 Incorrect 28 ms 464 KB too many queries. input: ? 371 2 1
21 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 6208 KB Output is correct
2 Correct 720 ms 6244 KB Output is correct
3 Correct 624 ms 6184 KB Output is correct
4 Correct 799 ms 6152 KB Output is correct
5 Correct 686 ms 6236 KB Output is correct
6 Correct 583 ms 6280 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 6748 KB Output is correct
2 Correct 771 ms 6644 KB Output is correct
3 Correct 680 ms 6512 KB Output is correct
4 Correct 846 ms 6644 KB Output is correct
5 Correct 623 ms 6660 KB Output is correct
6 Correct 672 ms 6564 KB Output is correct
7 Correct 709 ms 6600 KB Output is correct
8 Correct 840 ms 7764 KB Output is correct
9 Correct 894 ms 7588 KB Output is correct
10 Correct 659 ms 6916 KB Output is correct
11 Correct 640 ms 6860 KB Output is correct