Submission #442606

#	Time	Username	Problem	Language	Result	Execution time	Memory
442606		abc864197532	Worm Worries (BOI18_worm)	C++17	22 / 100	1667 ms	19592 KiB

worm

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define test(args...) abc("[" + string(#args) + "]", args)
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cerr << *l << " \n"[++l == r];
}
const int mod = 1e9 + 7, N = 200000;
 
map <array<int, 3>, int> m1;
int n, m, k, q, dx[6] = {1, -1, 0, 0, 0, 0}, dy[6] = {0, 0, 1, -1, 0, 0}, dz[6] = {0, 0, 0, 0, 1, -1};
 
int ask(int i, int j, int kk) {
    if (i < 0 || i >= n || j < 0 || j >= m || kk < 0 || kk >= k) return 0;
    if (!m1.count({i, j, kk})) {
        assert(q);
        cout << "? " << i + 1 << ' ' << j + 1 << ' ' << kk + 1 << endl;
        cin >> m1[{i, j, kk}];
        q--;
    }
    return m1[{i, j, kk}];
}
 
void chk(int i, int j, int kk) {
    bool is = true;
    for (int ii = 0; ii < 6; ++ii) {
        is &= ask(i, j, kk) >= ask(i + dx[ii], j + dy[ii], kk + dz[ii]);
    }
    if (is) {
        cout << "! " << i + 1 << ' ' << j + 1 << ' ' << kk + 1 << endl;
        exit(0);
    }
}
 
int main () {
    srand(time(NULL));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k >> q;
    if (m == 1 && k == 1) {
        // task 1 & 2
        int l = 0, r = n;
        while (r - l > 2) {
            int mid;
            if (rand() & 1) mid = (l + 3 * r) / 4;
            else mid = (l * 3 + r) / 4;
            if (ask(mid, 0, 0) > ask(mid + 1, 0, 0)) r = mid + 1;
            else l = mid + 1;
        }
        for (int i = l; i < r; ++i) chk(i, 0, 0);
    } else if (k == 1) {
        // task 3 & 4
        int l = 0, r = n;
        while (r - l > 5) {
            int mid = l + r >> 1;
            int mx1 = 0, mx2 = 0;
            for (int j = 0; j < m; ++j) {
                mx1 = max(mx1, ask(mid - 1, j, 0));
                mx2 = max(mx2, ask(mid, j, 0));
            }
            if (mx1 > mx2) r = mid;
            else l = mid;
        }
        for (int i = l; i < r; ++i) {
            for (int j = 0; j < m; ++j) {
                chk(i, j, 0);
            }
        }
        assert(false);
    } else {
        // task 5 & 6
        int l1 = 0, r1 = n, l2 = 0, r2 = m, l3 = 0, r3 = k;
        for (int _ = 0; _ < 6; ++_) {
            {
                int mid = l1 + r1 >> 1;
                int mx1 = 0, mx2 = 0;
                for (int i = l2; i < r2; ++i) for (int j = l3; j < r3; ++j) {
                    mx1 = max(mx1, ask(mid - 1, i, j));
                    mx2 = max(mx2, ask(mid, i, j));
                }
                if (mx1 > mx2) r1 = mid;
                else l1 = mid;
            }
            {
                int mid = l2 + r2 >> 1;
                int mx1 = 0, mx2 = 0;
                for (int i = l1; i < r1; ++i) for (int j = l3; j < r3; ++j) {
                    mx1 = max(mx1, ask(i, mid - 1, j));
                    mx2 = max(mx2, ask(i, mid, j));
                }
                if (mx1 > mx2) r2 = mid;
                else l2 = mid;
            }
            {
                int mid = l3 + r3 >> 1;
                int mx1 = 0, mx2 = 0;
                for (int i = l1; i < r1; ++i) for (int j = l2; j < r2; ++j) {
                    mx1 = max(mx1, ask(i, j, mid -1));
                    mx2 = max(mx2, ask(i, j, mid));
                }
                if (mx1 > mx2) r3 = mid;
                else l3 = mid;
            }
        }
        for (int i = l1; i < r1; ++i) for (int j = l2; j < r2; ++j) for (int k = l3; k < r3; ++k) {
            chk(i, j, k);
        }
        assert(false);
    }
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:67:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |             int mid = l + r >> 1;
      |                       ~~^~~
worm.cpp:87:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |                 int mid = l1 + r1 >> 1;
      |                           ~~~^~~~
worm.cpp:97:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |                 int mid = l2 + r2 >> 1;
      |                           ~~~^~~~
worm.cpp:107:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |                 int mid = l3 + r3 >> 1;
      |                           ~~~^~~~

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