oj.uz

Submission #56306

# Submission time Handle Problem Language Result Execution time Memory
56306 2018-07-11T03:53:50 Z model_code Worm Worries (BOI18_worm) C++17
81 / 100
 3000 ms 4688 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 500 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 624 KB Output is correct
2 Correct 6 ms 624 KB Output is correct
3 Correct 10 ms 624 KB Output is correct
4 Correct 18 ms 624 KB Output is correct
5 Correct 8 ms 624 KB Output is correct
6 Correct 15 ms 624 KB Output is correct
7 Correct 16 ms 624 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 624 KB Output is correct
2 Correct 7 ms 624 KB Output is correct
3 Correct 16 ms 624 KB Output is correct
4 Execution timed out 3074 ms 720 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 1652 KB Output is correct
2 Correct 319 ms 1740 KB Output is correct
3 Correct 250 ms 1764 KB Output is correct
4 Correct 375 ms 1764 KB Output is correct
5 Correct 292 ms 1908 KB Output is correct
6 Correct 330 ms 1908 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 2416 KB Output is correct
2 Correct 506 ms 2468 KB Output is correct
3 Correct 329 ms 2468 KB Output is correct
4 Correct 457 ms 2764 KB Output is correct
5 Correct 528 ms 2764 KB Output is correct
6 Correct 573 ms 2764 KB Output is correct
7 Correct 532 ms 3020 KB Output is correct
8 Correct 590 ms 3524 KB Output is correct
9 Correct 437 ms 3524 KB Output is correct
10 Correct 934 ms 4688 KB Output is correct
11 Correct 616 ms 4688 KB Output is correct