Submission #442545

#TimeUsernameProblemLanguageResultExecution timeMemory
442545abc864197532Worm Worries (BOI18_worm)C++17
0 / 100
42 ms4244 KiB
#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;

int ask(int i, int j, int kk) {
    if (i < 0 || i >= n || j < 0 || j >= m || kk < 0 || kk >= k) return 0;
    assert(q);
    if (m1.count({i, j, kk})) {
        cout << "? " << i + 1 << ' ' << j + 1 << ' ' << kk + 1 << endl;
        cin >> m1[{i, j, kk}];
        q--;
    }
    return m1[{i, j, kk}];
}

void ans(int i, int j, int k) {
    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 > 100) {
            int mid = l + r >> 1;
            if (ask(mid, 0, 0) > ask(mid + 1, 0, 0)) r = mid;
            else l = mid;
        }
        vector <int> a(n, 0);
        for (int i = l; i < r; ++i) {
            a[i] = ask(i, 0, 0);
        }
        for (int i = l; i < r; ++i) {
            if (i == 0) {
                if (a[i] >= a[i + 1]) ans(i, 0, 0);
            } else if (i == n - 1) {
                if (a[i - 1] <= a[i]) ans(i, 0, 0);
            } else {
                if (a[i] >= a[i - 1] && a[i] >= a[i + 1]) ans(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;
            else l = mid;
        }
        for (int i = l; i < r; ++i) {
            for (int j = 0; j < m; ++j) {
                if (ask(i, j, 0) >= ask(i - 1, j, 0) && ask(i, j, 0) >= ask(i + 1, j, 0) && ask(i, j, 0) >= ask(i, j - 1, 0) && ask(i, j, 0) >= ask(i, j + 1, 0)) {
                    ans(i, j, 0);
                }
            }
        }
        assert(false);
    } else {
        // task 5 & 6

    }
}

Compilation message (stderr)

worm.cpp: In function 'int main()':
worm.cpp:49:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             int mid = l + r >> 1;
      |                       ~~^~~
worm.cpp:70:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = l + r >> 1;
      |                       ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...