Submission #500547

#	Time	Username	Problem	Language	Result	Execution time	Memory
500547		LittleCube	Worm Worries (BOI18_worm)	C++14	59 / 100	803 ms	5680 KiB

worm

#include <bits/stdc++.h>
#define int long long

std::map<int, int> arr;
int N, M, K, Q;

int query(int x, int y, int z)
{
    if (1 <= x && x <= N && 1 <= y && y <= M && 1 <= z && z <= K && arr[x * (M * K) + y * K + z] == 0)
    {
        printf("? %lld %lld %lld\n", x, y, z);
        fflush(stdout);
        int ans = -1;
        (void)scanf("%lld", &ans);
        if (ans == -1)
            exit(0);
        arr[x * (M * K) + y * K + z] = ans;
    }
    return arr[x * (M * K) + y * K + z];
}

void guess(int x, int y, int z)
{
    printf("! %lld %lld %lld\n", x, y, z);
    exit(0);
}

const double phi = 0.618033988749894848204586;
std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());

signed main()
{
    (void)scanf("%lld %lld %lld %lld", &N, &M, &K, &Q);
    int bestX = 1, bestY = 1, bestZ = 1, bestAns = 0;
    int i = 1;
    for (; i <= Q / 2; i++)
    {
        int x = abs((int)rd()) % N + 1;
        int y = abs((int)rd()) % M + 1;
        int z = abs((int)rd()) % K + 1;
        assert(x <= N);
        assert(y <= M);
        assert(z <= K);
        int ans = query(x, y, z);
        if (ans > bestAns)
            bestAns = ans, bestX = x, bestY = y, bestZ = z;
    }
    while (1)
    {
        int x = bestX, y = bestY, z = bestZ;
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++)
                for (int dz = -1; dz <= 1; dz++)
                    if (abs(dx) + abs(dy) + abs(dz) == 1)
                    {
                        int ans = query(x + dx, y + dy, z + dz);
                        if (ans > bestAns)
                        {
                            bestAns = query(x + dx, y + dy, z + dz);
                            bestX = x + dx, bestY = y + dy, bestZ = z + dz;
                            goto next;
                        }
                    }
    next:
        bestX += 0;
        if (x == bestX && y == bestY && z == bestZ)
            break;
    }

    guess(bestX, bestY, bestZ);
}
// 1 4 2 5 8 | 4 2 5 4 2 | 1 4 2 5 8 | 4 2 5 4 2

Compilation message (stderr)

worm.cpp: In function 'long long int query(long long int, long long int, long long int)':
worm.cpp:14:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         (void)scanf("%lld", &ans);
      |               ~~~~~^~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:33:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     (void)scanf("%lld %lld %lld %lld", &N, &M, &K, &Q);
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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