Submission #1093792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093792		MateiKing80	Worm Worries (BOI18_worm)	C++17	100 / 100	689 ms	6992 KiB

worm

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, k, q;
map<tuple<int, int, int>, int> mp;

int rangerng(int left, int right)
{
    return left + abs(int(rng())) % (right - left + 1);
}

int ask(int x, int y, int z)
{
    if(mp.find(make_tuple(x, y, z)) != mp.end())
        return mp[make_tuple(x, y, z)];
    cout << "? " << x << " " << y << " " << z << endl;
    int ans;
    cin >> ans;
    mp[make_tuple(x, y, z)] = ans;
    return ans;
}

void answer(int x, int y, int z)
{
    cout << "! " << x << " " << y << " " << z << endl;
}

void subtask1()
{
    double aur = (1 + sqrt(5)) / 2;
    int st = 0, dr = n + 1;
    int mid = st + int((dr - st - 1) / aur) + 1;
    int val = ask(mid, 1, 1);
    while (dr - st > 2)
    {
        if (mid - st > dr - mid)
        {
            int mid1 = st + int((mid - st - 1) / aur) + 1;
            int val1 = ask(mid1, 1, 1);
            if (val < val1)
            {
                dr = mid;
                mid = mid1;
                val = val1;
            }
            else
                st = mid1;
        }
        else
        {
            int mid1 = dr - int((dr - mid - 1) / aur) - 1;
            int val1 = ask(mid1, 1, 1);
            if (val < val1)
            {
                st = mid;
                mid = mid1;
                val = val1;
            }
            else
                dr = mid1;
        }
    }
    answer(mid, 1, 1);
}

void solve(int i1, int j1, int i2, int j2, int i3, int j3, int a3, int sus)
{
    int i, j, nj, na;

    i = (i1 + i2) / 2;
    nj = na = -1;
    for (j = j1; j <= j2; j++)
    {
        int a = !sus ? ask(i, j, 1) : ask(j, i, 1);

        if (na < a)
            na = a, nj = j;
    }
    if (na < a3)
    {
        if (i3 < i)
            solve(j1, i1, j2, i - 1, j3, i3, a3, sus ^ 1);
        else
            solve(j1, i + 1, j2, i2, j3, i3, a3, sus ^ 1);
    }
    else if (i > i1 && na < (!sus ? ask(i - 1, nj, 1) : ask(nj, i - 1, 1)))
        solve(j1, i1, j2, i - 1, nj, i, na, sus ^ 1);
    else if (i < i2 && na < (!sus ? ask(i + 1, nj, 1) : ask(nj, i + 1, 1)))
        solve(j1, i + 1, j2, i2, nj, i, na, sus ^ 1);
    else if (!sus)
        answer(i, nj, 1);
    else
        answer(nj, i, 1);
}

void subtask2()
{
    solve(1, 1, n, m, -1, -1, -1, 0);
}

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

bool check(int x, int y, int z)
{
    return (x > 0 && x <= n && y > 0 && y <= m && z > 0 && z <= k);
}

void subtask3()
{
    int x, y, z, a = -1;
    for (int i = 1; i <= q / 2; i ++)
    {
        int nx = rangerng(1, n), ny = rangerng(1, m), nz = rangerng(1, k);
        int na = ask(nx, ny, nz);
        if (a < na)
        {
            a = na;
            x = nx;
            y = ny;
            z = nz;
        }
    }
    while(true)
    {
        bool ok = false;
        for (int i = 0; i < 6; i ++)
        {
            int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i];
            if(check(nx, ny, nz))
            {
                int na = ask(nx, ny, nz);
                if (a < na)
                {
                    a = na;
                    x = nx;
                    y = ny;
                    z = nz;
                    ok = true;
                    break;
                }
            }
        }
        if(!ok)
            break;
    }
    answer(x, y, z);
}

int main()
{
    cin >> n >> m >> k >> q;
    if (m == 1 && k == 1)
        subtask1();
    else if (k == 1)
        subtask2();
    else
        subtask3();
    return 0;
}

Compilation message (stderr)

worm.cpp: In function 'void subtask3()':
worm.cpp:151:11: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |     answer(x, y, z);
      |     ~~~~~~^~~~~~~~~
worm.cpp:151:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:151:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23