Submission #279698

#	Time	Username	Problem	Language	Result	Execution time	Memory
279698		evpipis	Worm Worries (BOI18_worm)	C++11	100 / 100	691 ms	5560 KiB

worm

#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 (stderr)

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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23