Submission #278778

#	Time	Username	Problem	Language	Result	Execution time	Memory
278778		evpipis	Worm Worries (BOI18_worm)	C++11	32 / 100	3046 ms	496 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);

        //printf("l = %d, r = %d\n", l, r);
        //printf("m1 = %d, m2 = %d\n", m1, m2);
        //assert(m1 < m2);
        //printf("%d vs %d\n", ask(m1), ask(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;
    while (true){
        if (r1-l1 >= r2-l2){
            int mid = (l1+r1)/2, a, b, mx = -1;
            for (int i = l2; i <= r2; i++)
                if (ask(mid, i) > mx)
                    mx = ask(mid, i), a = mid, b = i;

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

            if (check(a, b))
                answer(a, b);
            l2 = mid+1;
        }
    }

    answer(l1, l2);
}

void solve_3D(){
    return;
    int d = 500, ans = 0;
    while (d > 0){
        ans += d*d + d*d/2 + d*d/4;
        d /= 2;
    }

    printf("ans = %d\n", ans);
}

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:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'void solve_2D()':
worm.cpp:85:23: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |                 answer(a, b);
      |                 ~~~~~~^~~~~~
worm.cpp:85:23: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:75:23: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |                 answer(a, b);
      |                 ~~~~~~^~~~~~
worm.cpp:75:23: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

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