Submission #830626

#	Time	Username	Problem	Language	Result	Execution time	Memory
830626		Johann	Worm Worries (BOI18_worm)	C++14	100 / 100	897 ms	504376 KiB

worm

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>

const double PHI = 1.61803398874;

struct Coords {
    int x,y,z;
};

int ask(vvvi & H, int x, int y, int z) {
    if (x == 0 || x == H.size()-1 ||
        y == 0 || y == H[0].size()-1 ||
        z == 0 || z == H[0][0].size()-1) return 0;
    // int A[8][7] = {
    //         { 37, 36, 35, 34, 33, 32, 31 } ,
    //         { 1, 1, 1, 1, 1, 1, 30 },
    //         { 13, 12, 11, 10, 9, 1, 29 },
    //         { 14, 1, 1, 1, 8, 1, 28 },
    //         { 15, 1, 3, 1, 7, 1, 27 },
    //         { 16, 1, 4, 5, 6, 1, 26 },
    //         { 17, 1, 1, 1, 1, 1, 25 },
    //         { 18, 19, 20, 21, 22, 23, 24 }
    // };
    if (H[x][y][z] == -1) {
        printf("? %d %d %d\n", x, y, z);
        fflush(stdout);
        scanf("%d", &H[x][y][z]);
        // H[x][y][z] = A[y-1][x-1];
    }
    return H[x][y][z];
}
int ask(vvvi & H, Coords c) { return ask(H, c.x, c.y, c.z); }

Coords null = { -1, -1, -1 };
Coords getBetter(vvvi & H, int x, int y, int z) {
    int mValue = ask(H, x, y, z);
    Coords alt;
    vector<Coords> neighbors = {
            { x+1, y, z },
            { x-1, y, z },
            { x, y+1, z },
            { x, y-1, z },
            { x, y, z+1 },
            { x, y, z-1 }
    };
    for (Coords n : neighbors) {
        if (ask(H, n) > mValue) {
            mValue = ask(H, n);
            alt = n;
        }
    }
    if (mValue == ask(H, x, y, z)) return null;
    else return alt;
}
Coords getBetter(vvvi & H, Coords c) {  return getBetter(H, c.x, c.y, c.z);  }

int random(int n, mt19937 & rng) {
    return ((int) rng() % n + n) % n;
}

int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int N, M, K, Q;
    scanf("%d %d %d %d", &N, &M, &K, &Q);

    vvvi H(N+2, vvi(M+2, vi(K+2, -1)));

    if (K != 1) {
        Coords maxi = { 1, 1, 1 };
        int x, y, z;
        for (int i = 0; i < Q / 2; ++i) {
            x = random(N, rng) + 1;
            y = random(M, rng) + 1;
            z = random(K, rng) + 1;
            if (ask(H, x, y, z) > ask(H, maxi)) maxi = { x, y, z };
        }

        while (getBetter(H, maxi).x != -1) maxi = getBetter(H, maxi);
        printf("! %d %d %d", maxi.x, maxi.y, maxi.z);

    } else if (M != 1) {

        Coords maxi = { N, M, K };
        Coords tl = { 1, 1, 1};
        Coords br = {  N, M, K };
        bool vert = false;

        while (getBetter(H, maxi).x != -1) {
            Coords maxv = { 0, 0, 0 };
            int xw = (tl.x + br.x) / 2;
            int yw = (tl.y + br.y) / 2;
            int zw = (tl.z + br.z) / 2;
            if (vert) {
                for (yw = tl.y; yw <= br.y; ++yw) {
                    if (ask(H, xw, yw, zw) > ask(H, maxv)) maxv = { xw, yw, zw };
                }
            } else {
                for (xw = tl.x; xw <= br.x; ++xw) {
                    if (ask(H, xw, yw, zw) > ask(H, maxv)) maxv = { xw, yw, zw };
                }
            }
            if (getBetter(H, maxv).x == -1) { maxi = maxv; break; }
            else { maxv = getBetter(H, maxv); }

            if (ask(H, maxv) > ask(H, maxi))  maxi = maxv;
            if (vert) {
                if (maxi.x > xw) tl.x = xw+1;
                else br.x = xw-1;
            } else {
                if (maxi.y > yw) tl.y = yw+1;
                else br.y = yw-1;
            }
            vert = !vert;
        }

        printf("! %d %d %d", maxi.x, maxi.y, maxi.z);

    } else {
        int l = 0, r = N + 1, m = 1 / PHI * (r - l);

        while (r - l > 2) {
            bool right = (r - m > m - l);
            int mm;
            if (right) { // rechts ist größer...
                mm = ceil(r - 1.0 / PHI * (r - m));
                if (ask(H, mm, 1, 1) >= ask(H, m, 1, 1)) {
                    l = m;
                    m = mm;
                } else {
                    r = mm;
                }
            } else {
                mm = floor(l + 1 / PHI * (m - l));
                if (ask(H, mm, 1, 1) >= ask(H, m, 1, 1)) {
                    r = m;
                    m = mm;
                } else {
                    l = mm;
                }
            }
        }
        printf("! %d %d %d\n", m, 1, 1);
    }
    fflush(stdout);
}

Compilation message (stderr)

worm.cpp: In function 'int ask(std::vector<std::vector<std::vector<int> > >&, int, int, int)':
worm.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (x == 0 || x == H.size()-1 ||
      |                   ~~^~~~~~~~~~~~~
worm.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         y == 0 || y == H[0].size()-1 ||
      |                   ~~^~~~~~~~~~~~~~~~
worm.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         z == 0 || z == H[0][0].size()-1) return 0;
      |                   ~~^~~~~~~~~~~~~~~~~~~
worm.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d", &H[x][y][z]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d %d %d %d", &N, &M, &K, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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