Submission #537626

#	Time	Username	Problem	Language	Result	Execution time	Memory
537626		surgutti	Worm Worries (BOI18_worm)	C++17	10 / 100	1384 ms	502312 KiB

worm

#pragma GCC optimize ("Ofast,inline,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

int N, M, K, Q;

vector<int> p{0, 1, 2};

vector<vector<vector<int>>> safe;

int get(vector<int> pos, bool print = false) {

    vector<int> xyz(3);

    for (int i = 0; i < 3; i++) {
        xyz[p[i]] = pos[i];
    }

    int x = xyz[0];
    int y = xyz[1];
    int z = xyz[2];
    
    if (print) {
        cout << "! " << x << ' ' << y << ' ' << z << endl;
        return -1;
    }

    if (!safe[x][y][z]) {
        cout << "? " << x << ' ' << y << ' ' << z << endl;
        cin >> safe[x][y][z];
    }

    return safe[x][y][z];
}

int main() {
    // ios::sync_with_stdio(false), cin.tie(nullptr);  

    cin >> N >> M >> K >> Q;

    safe.resize(N + 1, vector(M + 1, vector<int>(K + 1)));
    
    vector<pair<int, int>> a = {{1, N}, {1, M}, {1, K}};

    while (true) {

        sort(p.begin(), p.end(), [&a](int i, int j) {
            return a[i].second - a[i].first > a[j].second - a[j].first;
        });

        int max_val = -1;
        vector<int> max_pos;

        if (a[p[0]].second - a[p[0]].first <= 2) {
            
            for (int i = a[p[0]].first; i <= a[p[0]].second; i++) {
                for (int j = a[p[1]].first; j <= a[p[1]].second; j++) {
                    for (int k = a[p[2]].first; k <= a[p[2]].second; k++) {
                        int cur_val = get({i, j, k});

                        if (cur_val > max_val) {
                            max_val = cur_val;
                            max_pos = {i, j, k};
                        }
                    }
                }
            }
        
            get(max_pos, true);
            
            return 0;
        }

        int m = (a[p[0]].first + a[p[0]].second) >> 1;
        
        for (int i = a[p[1]].first; i <= a[p[1]].second; i++) {
            for (int j = a[p[2]].first; j <= a[p[2]].second; j++) {
                int cur_val = get({m, i, j});
                
                if (cur_val > max_val) {
                    max_val = cur_val;
                    max_pos = {m, i, j};
                }
            }
        }

        vector<int> L_pos = max_pos;
        vector<int> R_pos = max_pos;

        L_pos[0]--;
        R_pos[0]++;

        if (get(L_pos) < get(R_pos)) {
            a[p[0]].first = m;
        }
        else {
            a[p[0]].second = m;
        }
    }
}

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