Submission #500538

#TimeUsernameProblemLanguageResultExecution timeMemory
500538LittleCubeWorm Worries (BOI18_worm)C++14
0 / 100
764 ms3824 KiB
#include <bits/stdc++.h>

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("? %d %d %d\n", x, y, z);
        fflush(stdout);
        int ans = -1;
        (void)scanf("%d", &ans);
        if (ans == -1)
            exit(0);
        arr[x * (M * K) + y * K + z] = ans;
    }
    return arr[x];
}

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

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

int main()
{
    (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
    int bestX, bestY, bestZ, bestAns = 0;
    int i = 1;
    for (; i <= Q / 2; i++)
    {
        int x = abs((long long)rd()) % N + 1, y = abs((long long)rd()) % M + 1, z = abs((long long)rd()) % K + 1;
        if (query(x, y, z) > bestAns)
            bestAns = query(x, y, z), bestX = x, bestY = y, bestZ = z;
    }
    for (; i + 5 <= Q; i += 6)
    {
        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(bestX + dx, bestY + dy, bestZ + dz);
                        if (ans > bestAns)
                        {
                            bestAns = query(bestX + dx, bestY + dy, bestZ + dz);
                            bestX += dx, bestY += dy, bestZ += dz;
                            goto next;
                        }
                    }
    next:
        bestX += 0;
    }
    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 'int query(int, int, int)':
worm.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         (void)scanf("%d", &ans);
      |               ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:32:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     (void)scanf("%d %d %d %d", &N, &M, &K, &Q);
      |           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp:59:10: warning: 'bestZ' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     guess(bestX, bestY, bestZ);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
worm.cpp:59:10: warning: 'bestY' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:59:10: warning: 'bestX' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...