Submission #680954

#	Time	Username	Problem	Language	Result	Execution time	Memory
680954		jhwest2	Worm Worries (BOI18_worm)	C++17	100 / 100	908 ms	5628 KiB

worm

#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 (stderr)

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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23