제출 #550985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550985		thuanqvbn03	Worm Worries (BOI18_worm)	C++17	100 / 100	789 ms	5796 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);
}

const int dx[6] = {1, -1, 0, 0, 0, 0};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const 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 = genInt(1, n), ny = genInt(1, m), nz = genInt(1, k);
        int na = ask(nx, ny, nz);
        if (a < na)
        {
            a = na;
            x = nx;
            y = ny;
            z = nz;
        }
    }
    while (true)
    {
        bool flag = 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;
                    flag = true;
                    break;
                }
            }
        }
        if (!flag)
        {
            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;
}

컴파일 시 표준 에러 (stderr) 메시지

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