oj.uz

Submission #279698

# Submission time Handle Problem Language Result Execution time Memory
279698 2020-08-22T09:57:30 Z evpipis Worm Worries (BOI18_worm) C++11
100 / 100
 691 ms 5560 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, k, q;
map<tuple<int, int, int>, int> mym;

int ask(int a = 1, int b = 1, int c = 1){
    if (a < 1 || b < 1 || c < 1 || a > n || b > m || c > k)
        return 0;
    if (mym.count(make_tuple(a, b, c)))
        return mym[make_tuple(a, b, c)];

    printf("? %d %d %d\n", a, b, c), fflush(stdout);

    int ans;
    scanf("%d", &ans);
    if (ans == -1) exit(0);
    return mym[make_tuple(a, b, c)] = ans;
}

void answer(int a = 1, int b = 1, int c = 1){
    printf("! %d %d %d\n", a, b, c), fflush(stdout);
    exit(0);
}

bool check(int a = 1, int b = 1, int c = 1){
    if (max(ask(a-1, b, c), ask(a+1, b, c)) > ask(a, b, c))
        return false;
    if (max(ask(a, b-1, c), ask(a, b+1, c)) > ask(a, b, c))
        return false;
    if (max(ask(a, b, c-1), ask(a, b, c+1)) > ask(a, b, c))
        return false;
    return true;
}

void solve_1D(){
    int l = 1, r = n, m1, m2, keep = 0;
    while (l < r){
        swap(m1, m2);
        if (keep != 1)
            m1 = ceil(0.62*l + 0.38*r);
        if (keep != 2)
            m2 = floor(0.38*l + 0.62*r);

        if (m1 > m2)
            swap(m1, m2);
        if (m1 == m2)
            (l < m1 ? m1-- : m2++);
        assert(m1 < m2);

        if (ask(m1) >= ask(m2))
            r = m2-1, keep = 2;
        else
            l = m1+1, keep = 1;
    }

    answer(l);
}

void solve_2D(){
    int l1 = 1, r1 = n, l2 = 1, r2 = m, x = 0, y = 0;
    while (l1 < r1 || l2 < r2){
        if (r1-l1 >= r2-l2){
            int mid = (l1+r1)/2, a = mid, b = l2;
            for (int i = l2; i <= r2; i++)
                if (ask(mid, i) > ask(a, b))
                    a = mid, b = i;

            if (ask(a, b) < ask(x, y))
                (x > a ? l1 = mid+1 : r1 = mid-1);
            else if (ask(a+1, b) > ask(a, b))
                l1 = mid+1, x = a, y = b;
            else if (ask(a-1, b) > ask(a, b))
                r1 = mid-1, x = a, y = b;
            else
                answer(a, b);
        }
        else{
            int mid = (l2+r2)/2, a = l1, b = mid;
            for (int i = l1; i <= r1; i++)
                if (ask(i, mid) > ask(a, b))
                    a = i, b = mid;

            if (ask(a, b) < ask(x, y))
                (y > mid ? l2 = mid+1 : r2 = mid-1);
            else if (ask(a, b+1) > ask(a, b))
                l2 = mid+1, x = a, y = b;
            else if (ask(a, b-1) > ask(a, b))
                r2 = mid-1, x = a, y = b;
            else
                answer(a, b);
        }
    }

    answer(l1, l2);
}

void solve_3D(){
    int tries = 50000, x = 0, y = 0, z = 0;

    while (tries--){
        int a = rand()%n+1, b = rand()%m+1, c = rand()%k+1;
        if (ask(a, b, c) > ask(x, y, z))
            x = a, y = b, z = c;
    }

    int da[] = {0, 0, 0, 0, 1, -1};
    int db[] = {0, 0, 1, -1, 0, 0};
    int dc[] = {1, -1, 0, 0, 0, 0};
    while (true){
        int a, b, c, local = 1;
        for (int d = 0; d < 6; d++){
            a = x+da[d];
            b = y+db[d];
            c = z+dc[d];

            if (ask(a, b, c) > ask(x, y, z)){
                local = 0;
                break;
            }
        }

        if (local)
            answer(x, y, z);
        x = a, y = b, z = c;
    }
}

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &q);

    if (k > 1)
        solve_3D();
    else if (m > 1)
        solve_2D();
    else
        solve_1D();
    return 0;
}

Compilation message

worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |     scanf("%d", &ans);
      |     ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 38 ms 504 KB Output is correct
3 Correct 10 ms 384 KB Output is correct
4 Correct 38 ms 492 KB Output is correct
5 Correct 33 ms 436 KB Output is correct
6 Correct 32 ms 648 KB Output is correct
7 Correct 30 ms 500 KB Output is correct
8 Correct 32 ms 532 KB Output is correct
9 Correct 30 ms 552 KB Output is correct
10 Correct 30 ms 504 KB Output is correct
11 Correct 30 ms 576 KB Output is correct
12 Correct 25 ms 652 KB Output is correct
13 Correct 30 ms 536 KB Output is correct
14 Correct 36 ms 504 KB Output is correct
15 Correct 32 ms 672 KB Output is correct
16 Correct 31 ms 504 KB Output is correct
17 Correct 26 ms 504 KB Output is correct
18 Correct 30 ms 500 KB Output is correct
19 Correct 26 ms 504 KB Output is correct
20 Correct 17 ms 412 KB Output is correct
21 Correct 30 ms 504 KB Output is correct
22 Correct 24 ms 504 KB Output is correct
23 Correct 34 ms 504 KB Output is correct
24 Correct 30 ms 504 KB Output is correct
25 Correct 24 ms 460 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 3512 KB Output is correct
2 Correct 578 ms 3500 KB Output is correct
3 Correct 589 ms 3448 KB Output is correct
4 Correct 566 ms 3524 KB Output is correct
5 Correct 532 ms 3392 KB Output is correct
6 Correct 465 ms 3432 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 3588 KB Output is correct
2 Correct 523 ms 3564 KB Output is correct
3 Correct 572 ms 3608 KB Output is correct
4 Correct 583 ms 3956 KB Output is correct
5 Correct 511 ms 3948 KB Output is correct
6 Correct 468 ms 3576 KB Output is correct
7 Correct 611 ms 4128 KB Output is correct
8 Correct 525 ms 4000 KB Output is correct
9 Correct 434 ms 3704 KB Output is correct
10 Correct 691 ms 5560 KB Output is correct
11 Correct 623 ms 4000 KB Output is correct