Submission #550981

#	Time	Username	Problem	Language	Result	Execution time	Memory
550981		thuanqvbn03	Worm Worries (BOI18_worm)	C++17	63 / 100	1299 ms	9836 KiB

worm

#include <bits/stdc++.h>

using namespace std;

mt19937 rd(20030101);

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

int genInt(int left, int right)
{
    return left + abs(int(rd())) % (right - left + 1);
}

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

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

void subtask1()
{
    double phi = (1 + sqrt(5)) / 2;
    int left = 0, right = n + 1;
    int mid = left + int((right - left - 1) / phi) + 1;
    int val = ask(mid, 1, 1);
    while (right - left > 2)
    {
        if (mid - left > right - mid)
        {
            int mid_ = left + int((mid - left - 1) / phi) + 1;
            int val_ = ask(mid_, 1, 1);
            if (val < val_)
            {
                right = mid;
                mid = mid_;
                val = val_;
            }
            else
            {
                left = mid_;
            }
        }
        else
        {
            int mid_ = right - int((right - mid - 1) / phi) - 1;
            int val_ = ask(mid_, 1, 1);
            if (val < val_)
            {
                left = mid;
                mid = mid_;
                val = val_;
            }
            else
            {
                right = mid_;
            }
        }
    }
    answer(mid, 1, 1);
}

void solve(int i1, int j1, int i2, int j2, int i3, int j3, int a3, int flip) {
	int i, j, j_, a_;
 
	i = (i1 + i2) / 2;
	j_ = a_ = -1;
	for (j = j1; j <= j2; j++) {
		int a = !flip ? ask(i, j, 1) : ask(j, i, 1);
 
		if (a_ < a)
			a_ = a, j_ = j;
	}
	if (a_ < a3) {
		if (i3 < i)
			solve(j1, i1, j2, i - 1, j3, i3, a3, flip ^ 1);
		else
			solve(j1, i + 1, j2, i2, j3, i3, a3, flip ^ 1);
	} else if (i > i1 && a_ < (!flip ? ask(i - 1, j_, 1) :ask(j_, i - 1, 1)))
		solve(j1, i1, j2, i - 1, j_, i, a_, flip ^ 1);
	else if (i < i2 && a_ < (!flip ? ask(i + 1, j_, 1) : ask(j_, i + 1, 1)))
		solve(j1, i + 1, j2, i2, j_, i, a_, flip ^ 1);
	else if (!flip)
		answer(i, j_, 1);
	else
		answer(j_, i, 1);
}

void subtask2()
{
    solve(1, 1, n, m, -1, -1, -1, 0);
}
void subtask3()
{
    int h, i, j, l, a, i_, j_, l_, a_;
    i_ = j_ = l_ = a_ = -1;
    for (h = 0; h < q / 2; h++)
    {
        i = genInt(1, n), j = genInt(1, m), l = genInt(1, k), a = ask(i, j, k);
        if (a_ < a)
        {
            a_ = a, i_ = i, j_ = j, l_ = l;
        }
    }
    i = i_, j = j_, l = l_, a = a_;
    while (1)
    {
        if (i > 1 && a < (a_ = ask(i - 1, j, l)))
        {
            a = a_, i--;
        }
        else if (i < n && a < (a_ = ask(i + 1, j, l)))
        {
            a = a_, i++;
        }
        else if (j > 1 && a < (a_ = ask(i, j - 1, l)))
        {
            a = a_, j--;
        }
        else if (j < m && a < (a_ = ask(i, j + 1, l)))
        {
            a = a_, j++;
        }
        else if (l > 1 && a < (a_ = ask(i, j, l - 1)))
        {
            a = a_, l--;
        }
        else if (l < k && a < (a_ = ask(i, j, l + 1)))
        {
            a = a_, l++;
        }
        else
        {
            break;
        }
    }
    answer(i, j, l);
}

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

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