oj.uz

Submission #825372

# Submission time Handle Problem Language Result Execution time Memory
825372 2023-08-14T18:56:18 Z QwertyPi Worm Worries (BOI18_worm) C++14
69 / 100
 864 ms 7720 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 <= 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

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 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

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 0 ms 208 KB Output is correct
6 Correct 1 ms 220 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 360 KB out of bounds (too large). input: ? 39 139 2
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 404 KB out of bounds (too large). input: ? 875 345 2
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 6260 KB Output is correct
2 Correct 725 ms 6200 KB Output is correct
3 Correct 638 ms 6244 KB Output is correct
4 Correct 727 ms 6344 KB Output is correct
5 Correct 597 ms 6204 KB Output is correct
6 Correct 564 ms 6280 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 6440 KB Output is correct
2 Correct 629 ms 6476 KB Output is correct
3 Correct 745 ms 6512 KB Output is correct
4 Correct 780 ms 6688 KB Output is correct
5 Correct 753 ms 6488 KB Output is correct
6 Correct 815 ms 6668 KB Output is correct
7 Correct 864 ms 6588 KB Output is correct
8 Correct 776 ms 7720 KB Output is correct
9 Correct 708 ms 6616 KB Output is correct
10 Correct 789 ms 6556 KB Output is correct
11 Correct 799 ms 6852 KB Output is correct