Submission #56306

#	Time	Username	Problem	Language	Result	Execution time	Memory
56306		model_code	Worm Worries (BOI18_worm)	C++17	81 / 100	3074 ms	4688 KiB

worm

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int n, m, K, Q;
double tp = 1.618034;
int G[1010000], DEBUG = 0, GG[110][110][110];
int Get(int x, int y, int z) {
    if (x<1 || x>n || y<1 || y>m || z<1 || z>K)return 0;
    Q--;
    if (Q < 0) {
        while (1) {}
    }
    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    int a;
    if (!DEBUG)scanf("%d", &a);
    else a = GG[x][y][z];
    return a;
}
int vv[1010000], ww[1010000];
int Mid11(int b, int e) {
    return round((b*tp + e) / (tp + 1));
}
int Mid12(int b, int e) {
    return round((b + e*tp) / (tp + 1));
}
void Go1(int b, int e, int m1, int m2) {
    if (e - b <= 4) {
        int i;
        for (i = b; i <= e; i++) {
            if (!vv[i]) {
                ww[i] = Get(i, 1, 1);
            }
        }
        for (i = b + 1; i <= e - 1; i++) {
            if (ww[i - 1] <= ww[i] && ww[i] >= ww[i + 1]) {
                printf("! %d %d %d\n", i, 1, 1);
                return;
            }
        }
    }
    if (m1 == -1) {
        m1 = Mid11(b, e);
        ww[m1] = Get(m1, 1, 1);
    }
    if (m2 == -1) {
        m2 = Mid12(b, e);
        ww[m2] = Get(m2, 1, 1);
    }
    if (ww[m1] <= ww[m2]) {
        Go1(m1, e, m2, -1);
    }
    else {
        Go1(b, m2, -1, m1);
    }
}
void Solve1() {
    int b = 0, e = n + 1;
    vv[b] = vv[e] = 1;
    Go1(0, n + 1, -1, -1);
}
void Solve2() {
}
map<int, int>Map;
int Num3(int x, int y, int z) {
    return x * 1001 * 1001 + y * 1001 + z;
}
int Get3(int x, int y, int z) {
    if (x<1 || x>n || y<1 || y>m || z<1 || z>K)return 0;
    if (Map.count(Num3(x, y, z)))return Map[Num3(x, y, z)];
    return Map[Num3(x, y, z)] = Get(x, y, z);
}
int dx[6] = { 1,-1,0,0,0,0 }, dy[6] = { 0,0,1,-1,0,0 }, dz[6] = { 0,0,0,0,-1,1 };
void Solve3() {
    int x, y, z, i, r[6], px ,py, pz;
    int M = -1;
    for (i = 0; i < Q / 3; i++) {
        x = rand() % n + 1, y = rand() % m + 1, z = rand() % K + 1;
        if (M < Get3(x, y, z)) {
            M = Get3(x, y, z);
            px = x, py = y, pz = z;
        }
    }
    x = px, y = py, z = pz;
    while (1) {
        int t = Get3(x, y, z), M = -1, pv = -1;
        for (i = 0; i < 6; i++) {
            r[i] = Get3(x + dx[i], y + dy[i], z + dz[i]);
            if (M < r[i])M = r[i], pv = i;
        }
        if (M <= t) {
            printf("! %d %d %d\n", x, y, z);
            return;
        }
        x += dx[pv], y += dy[pv], z += dz[pv];
    }
}
int main() {
    if (!DEBUG)scanf("%d%d%d%d", &n, &m, &K, &Q);
    else {
        n = m = K = 100;
        Q = 100000;
        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)for (int k = 1; k <= K; k++)GG[i][j][k] = rand() % 100 + 1;
    }
    if (m == 1 && K == 1) {
        Solve1();
    }
    else {
        Solve3();
    }
}

Compilation message (stderr)

worm.cpp: In function 'int Get(int, int, int)':
worm.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     if (!DEBUG)scanf("%d", &a);
                ~~~~~^~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:102:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     if (!DEBUG)scanf("%d%d%d%d", &n, &m, &K, &Q);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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