oj.uz

Submission #550985

# Submission time Handle Problem Language Result Execution time Memory
550985 2022-04-19T15:53:19 Z thuanqvbn03 Worm Worries (BOI18_worm) C++17
100 / 100
 789 ms 5796 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 7 ms 336 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 6 ms 308 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 5 ms 336 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 336 KB Output is correct
2 Correct 27 ms 364 KB Output is correct
3 Correct 9 ms 348 KB Output is correct
4 Correct 19 ms 452 KB Output is correct
5 Correct 28 ms 488 KB Output is correct
6 Correct 27 ms 612 KB Output is correct
7 Correct 27 ms 356 KB Output is correct
8 Correct 31 ms 448 KB Output is correct
9 Correct 25 ms 404 KB Output is correct
10 Correct 34 ms 356 KB Output is correct
11 Correct 25 ms 352 KB Output is correct
12 Correct 25 ms 420 KB Output is correct
13 Correct 27 ms 456 KB Output is correct
14 Correct 30 ms 456 KB Output is correct
15 Correct 30 ms 340 KB Output is correct
16 Correct 30 ms 444 KB Output is correct
17 Correct 27 ms 452 KB Output is correct
18 Correct 27 ms 440 KB Output is correct
19 Correct 30 ms 444 KB Output is correct
20 Correct 17 ms 364 KB Output is correct
21 Correct 28 ms 388 KB Output is correct
22 Correct 29 ms 348 KB Output is correct
23 Correct 27 ms 400 KB Output is correct
24 Correct 21 ms 456 KB Output is correct
25 Correct 27 ms 352 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 3256 KB Output is correct
2 Correct 368 ms 3332 KB Output is correct
3 Correct 406 ms 3280 KB Output is correct
4 Correct 440 ms 3548 KB Output is correct
5 Correct 381 ms 3376 KB Output is correct
6 Correct 438 ms 3436 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 4892 KB Output is correct
2 Correct 600 ms 5004 KB Output is correct
3 Correct 639 ms 4980 KB Output is correct
4 Correct 565 ms 5108 KB Output is correct
5 Correct 727 ms 5664 KB Output is correct
6 Correct 597 ms 5332 KB Output is correct
7 Correct 690 ms 5360 KB Output is correct
8 Correct 703 ms 5736 KB Output is correct
9 Correct 480 ms 4980 KB Output is correct
10 Correct 789 ms 5796 KB Output is correct
11 Correct 680 ms 5112 KB Output is correct