Submission #712085

#	Time	Username	Problem	Language	Result	Execution time	Memory
712085		wenqi	Worm Worries (BOI18_worm)	C++17	10 / 100	1 ms	208 KiB

worm

// trans rights
#include <bits/extc++.h>
using namespace std;
using ll = long long;

int N, M, K, Q;

map<tuple<int, int, int>, int> mp;

int H(int x, int y = 1, int z = 1)
{
    if (x < 1 or x > N)
        return 0;
    if (y < 1 or y > M)
        return 0;
    if (z < 1 or z > K)
        return 0;
    if (mp[{x, y, z}])
        return mp[{x, y, z}];
    cout << "? " << x << ' ' << y << ' ' << z << endl;
    int h;
    cin >> h;
    return mp[{x, y, z}] = h;
}

int main(int argc, const char *argv[])
{
    srand(420 * 420 + 13);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K >> Q;
    int a = 1, b = (1 << 20) + 1;
    while (b - a > 1)
    {
        int m = (a + b) / 2;
        if (m > N)
            b = m;

        int m1 = (a + m) / 2;
        int m2 = (m + b) / 2;
        if (rand() & 1)
        {
            if (H(m1) >= H(m))
            {
                b = m;
            }
            else if (H(m2) >= H(m))
            {
                a = m;
            }
            else
            {
                a = m1;
                b = m2;
            }
        }
        else
        {
            if (H(m2) >= H(m))
            {
                a = m;
            }
            else if (H(m1) >= H(m))
            {
                b = m;
            }
            else
            {
                a = m1;
                b = m2;
            }
        }
    }
    cout << "! " << a << ' ' << 1 << ' ' << 1;
    return 0;
}

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