Submission #712080

#	Time	Username	Problem	Language	Result	Execution time	Memory
712080		wenqi	Worm Worries (BOI18_worm)	C++17	10 / 100	1 ms	316 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 (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[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K >> Q;
    int a = 1, b = N + 1;
    bool t = true;
    while (b - a > 1)
    {
        if (t)
        {
            int s = b - a;
            int m1 = a + s / 3;
            int m2 = a + 2 * s / 3;
            if (H(m1) > H(m2))
            {
                b = m2;
            }
            else
            {
                a = m1 + 1;
            }
        }
        else
        {
            int m = (a + b) / 2;
            if (H(m) > H(m - 1))
                a = m;
            else
                b = m;
        }
        t = not t;
    }
    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