oj.uz

Submission #680954

# Submission time Handle Problem Language Result Execution time Memory
680954 2023-01-12T06:10:41 Z jhwest2 Worm Worries (BOI18_worm) C++17
100 / 100
 908 ms 5628 KB 
#include <bits/stdc++.h>
using namespace std;

const int dx[6] = {1, 0, 0, -1, 0, 0};
const int dy[6] = {0, 1, 0, 0, -1, 0};
const int dz[6] = {0, 0, 1, 0, 0, -1};

int n, m, k, q, cnt;
map<array<int, 3>, int> cache;

mt19937 rnd(15571557);
int rng(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rnd);
}

int ask(int x, int y = 1, int z = 1) {
    if (cache.find({x, y, z}) != cache.end())
        return cache[{x, y, z}];

    cout << "? " << x << ' ' << y << ' ' << z << endl;
    int res; cin >> res;
    ++cnt;
    return cache[{x, y, z}] = res;
}
array<int, 3> go(int x, int y = 1, int z = 1) {
    int v = ask(x, y, z);
    array<int, 3> res = {x, y, z};

    for (int t = 0; t < 6; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];
        int nz = z + dz[t];

        if (1 <= nx && nx <= n && 1 <= ny && ny <= m && 1 <= nz && nz <= k)
            if (v < ask(nx, ny, nz))
                v = ask(nx, ny, nz), res = {nx, ny, nz};
    }
    return res;
}
void solve_1D() {
    int L = 1, R = n;
    int p = (int)((L * 1.618 + R) / 2.618);
    while (R - L > 4) {
        int M;
        if (p < (L + R) / 2)
            M = (int)((L + R * 1.618) / 2.618);
        else
            M = (int)((L * 1.618 + R) / 2.618);
        
        if (ask(M) > ask(p)) {
            if (p < M)
                L = p + 1;
            else
                R = p - 1;

            p = M;
        }
        else {
            if (p < M)
                R = M - 1;
            else
                L = M + 1;
        }
    }
    for (int i = L; i <= R; i++) {
        auto [x, _, __] = go(i);
        if (x == i) {
            cout << "! " << x << ' ' << 1 << ' ' << 1 << endl;
            return;
        }
    }
}
void solve_2D() {
    int sx = 1, ex = n, sy = 1, ey = m;
    bool flag = 0;

    int maxv = -1, lx, ly;
    while (sx < ex || sy < ey) {
        if (flag) {
            int mx = (sx + ex) / 2;

            int p = -1; 
            for (int i = sy; i <= ey; i++)
                if (p == -1 || ask(mx, p) < ask(mx, i))
                    p = i;

            auto [nx, ny, _] = go(mx, p);

            if (nx == mx && ny == p) {
                sx = ex = mx;
                sy = ey = p;
                break;
            }
            if (ask(mx, p) > maxv) {
                maxv = ask(mx, p);
                lx = nx;
                ly = ny;
            }

            if (lx <= mx)
                ex = mx;
            else
                sx = mx + 1;            
        }
        else {
            int my = (sy + ey) / 2;

            int p = -1;
            for (int i = sx; i <= ex; i++)
                if (p == -1 || ask(p, my) < ask(i, my))
                    p = i;
            
            auto [nx, ny, _] = go(p, my);
            if (nx == p && ny == my) {
                sx = ex = p;
                sy = ey = my;
                break;
            }
            if (ask(p, my) > maxv) {
                maxv = ask(p, my);
                lx = nx;
                ly = ny;
            }

            if (ly <= my)
                ey = my;
            else
                sy = my + 1;
        }
        flag ^= 1;
    }
    cout << "! " << sx << ' ' << sy << ' ' << 1 << endl;
}
void solve_3D() {
    int v = -1, px, py, pz;
    while (cnt < q / 2) {
        int x = rng(1, n);
        int y = rng(1, m);
        int z = rng(1, k);

        if (v < ask(x, y, z)) {
            v = ask(x, y, z);
            px = x;
            py = y;
            pz = z;
        }
    }
    while (go(px, py, pz) != array<int, 3>{px, py, pz}) {
        auto [nx, ny, nz] = go(px, py, pz);
        px = nx;
        py = ny;
        pz = nz;
    }
    cout << "! " << px << ' ' << py << ' ' << pz << endl;
}
int main() {
    cin >> n >> m >> k >> q;
    if (m == 1 && k == 1)
        solve_1D();
    else if (k == 1)
        solve_2D();
    else 
        solve_3D();
}

Compilation message

worm.cpp: In function 'void solve_2D()':
worm.cpp:125:13: warning: 'ly' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             if (ly <= my)
      |             ^~
worm.cpp: In function 'void solve_3D()':
worm.cpp:154:47: warning: 'pz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |     cout << "! " << px << ' ' << py << ' ' << pz << endl;
      |                                               ^~
worm.cpp:154:40: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |     cout << "! " << px << ' ' << py << ' ' << pz << endl;
      |                                        ^~~
worm.cpp:154:27: warning: 'px' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |     cout << "! " << px << ' ' << py << ' ' << pz << endl;
      |                           ^~~

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 1 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 8 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 3 ms 208 KB Output is correct
2 Correct 4 ms 316 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 6 ms 332 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 7 ms 336 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 320 KB Output is correct
2 Correct 27 ms 464 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 32 ms 472 KB Output is correct
5 Correct 30 ms 396 KB Output is correct
6 Correct 35 ms 452 KB Output is correct
7 Correct 30 ms 444 KB Output is correct
8 Correct 25 ms 352 KB Output is correct
9 Correct 30 ms 392 KB Output is correct
10 Correct 28 ms 344 KB Output is correct
11 Correct 35 ms 352 KB Output is correct
12 Correct 26 ms 404 KB Output is correct
13 Correct 30 ms 460 KB Output is correct
14 Correct 30 ms 452 KB Output is correct
15 Correct 31 ms 456 KB Output is correct
16 Correct 26 ms 464 KB Output is correct
17 Correct 29 ms 424 KB Output is correct
18 Correct 27 ms 408 KB Output is correct
19 Correct 33 ms 420 KB Output is correct
20 Correct 20 ms 396 KB Output is correct
21 Correct 24 ms 460 KB Output is correct
22 Correct 31 ms 440 KB Output is correct
23 Correct 28 ms 424 KB Output is correct
24 Correct 30 ms 448 KB Output is correct
25 Correct 32 ms 440 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 3352 KB Output is correct
2 Correct 432 ms 3332 KB Output is correct
3 Correct 403 ms 3496 KB Output is correct
4 Correct 494 ms 3392 KB Output is correct
5 Correct 425 ms 3384 KB Output is correct
6 Correct 418 ms 3444 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 4864 KB Output is correct
2 Correct 728 ms 5004 KB Output is correct
3 Correct 680 ms 5080 KB Output is correct
4 Correct 790 ms 5336 KB Output is correct
5 Correct 908 ms 5628 KB Output is correct
6 Correct 641 ms 5020 KB Output is correct
7 Correct 632 ms 5068 KB Output is correct
8 Correct 721 ms 5420 KB Output is correct
9 Correct 445 ms 5236 KB Output is correct
10 Correct 774 ms 5160 KB Output is correct
11 Correct 709 ms 5292 KB Output is correct