oj.uz

Submission #537285

# Submission time Handle Problem Language Result Execution time Memory
537285 2022-03-14T21:44:47 Z surgutti Martian DNA (BOI18_dna) C++17
0 / 100
 2000 ms 1048576 KB 
#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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 161524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 603 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -