Submission #442554

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
442554	2021-07-08T07:44:05 Z	abc864197532	Worm Worries (BOI18_worm)	C++17	22 / 100	33 ms	1012 KB

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 k) {
    bool is = true;
    for (int ii = 0; ii < 6; ++ii) {
        is &= ask(i, j, k) >= ask(i + dx[ii], j + dy[ii], k + dz[ii]);
    }
    if (is) {
        cout << "! " << i + 1 << ' ' << j + 1 << ' ' << k + 1 << endl;
        exit(0);
    }
}

int main () {
    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 = l + r >> 1;
            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, j, 0));
                mx2 = max(mx2, ask(mid + 1, j, 0));
            }
            if (mx1 > mx2) r = mid + 1;
            else l = mid + 1;
        }
        for (int i = l; i < r; ++i) {
            for (int j = 0; j < m; ++j) {
                chk(i, j, 0);
            }
        }
        assert(false);
    } else {
        // task 5 & 6

    }
}

Compilation message

worm.cpp: In function 'int main()':
worm.cpp:55:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             int mid = l + r >> 1;
      |                       ~~^~~
worm.cpp:64:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	436 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	328 KB	Output is correct
2	Correct	32 ms	420 KB	Output is correct
3	Correct	18 ms	328 KB	Output is correct
4	Correct	19 ms	360 KB	Output is correct
5	Correct	29 ms	576 KB	Output is correct
6	Correct	21 ms	320 KB	Output is correct
7	Correct	31 ms	448 KB	Output is correct