제출 #1263846

#제출 시각아이디문제언어결과실행 시간메모리
1263846niepamietamhaslaWorm Worries (BOI18_worm)C++20
59 / 100
236 ms4936 KiB
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
typedef long double ld;

int n, m, k, q;
map<ll, int> pamiec;

vector<pair<int,pii>> roza = {{0,{0,1}},{0,{0,-1}},{0,{1,0}},{0,{-1,0}},{1,{0,0}},{-1,{0,0}}};

// const int MAXN = 1e6 + 5;

// int H[MAXN];

// int cnt = 0;

int pars(int x, int y, int z){
    if(x < 1 or x > n or y < 1 or y > m or z < 1 or z > k) return 0;
    ll G = x - 1 + (y-1) * n + (z-1) *n*m;
    if(pamiec.find(G) != pamiec.end()) return pamiec[G];
    cout << "? " << x << " " << y << " " << z << "\n";
    cin >> pamiec[G];
    // ll T = H[x];
    // cnt++;
    // pamiec[G] = T;
    return pamiec[G];
}

pair<int, pii> synowie(int x, int y, int z){
    int curr = pars(x, y, z);
    for(auto u : roza){
        int x2 = x + u.first;
        int y2 = y + u.second.first;
        int z2 = z + u.second.second;
        if(pars(x2,y2,z2) > curr) return {x2, {y2,z2}}; 
    }
    return {-1, {-1, -1}};
}

int znajdz1d(int a, int b, pii znane){
    if(a == b) return a;
    if(b - a + 1 <= 5){
        for(int i = a; i <= b; ++i){
            int lewo = pars(i-1, 1, 1);
            int curr = pars(i, 1, 1);
            int prawo = pars(i+1, 1, 1);
            if(curr >= lewo and curr >= prawo){
                return i;
            }
        }
    }

    pii split = znane;
    if(split.first == -1){
        split.first = (0.618 * (ld)a + 0.382 * (ld)b);
    }
    if(split.second == -1){
        split.second = ((ld)0.382 * (ld)a + (ld)0.618 * (ld)b);
    }
    //cout << split.first << " " << split.second << " spl\n";
    if(split.first == a){
        split.first++;
    }
    if(split.second == b){
        split.second--;
    }
    int L1 = pars(split.first, 1, 1);
    int L2 = pars(split.second, 1, 1);
    //cout << L1 << " " << L2 << " L\n";
    if(L1 >= L2){
        return znajdz1d(a, split.second - 1, {-1, split.first});
    }
    else{
        return znajdz1d(split.first + 1, b, {split.second, -1});
    }

    // if(a == b) return a;
    // if(b - a + 1 <= 3){
    //     for(int i = a; i <= b; ++i){
    //         int lewo = pars(i-1, 1, 1);
    //         int curr = pars(i, 1, 1);
    //         int prawo = pars(i+1, 1, 1);
    //         if(curr >= lewo and curr >= prawo){
    //             return i;
    //         }
    //     }
    // }
    // ll mid = (a + b) / 2;
    // ll nxt = mid + 1;
    // int L1 = pars(mid, 1, 1);
    // int L2 = pars(nxt, 1, 1);
    // if(L1 >= L2){
    //     return znajdz1d(a, mid, {-1,-1});
    // }
    // else{
    //     return znajdz1d(nxt, b, {-1, -1});
    // }

}

int main(){
    cin >> n >> m >> k >> q;
    // for(int i = 1; i <= n; ++i){
    //     cin >> H[i];
    // }
    if(m == 1 and k == 1 and q <= 35){
        int x = znajdz1d(1, n, {-1, -1});
        cout << "! " << x << " " << 1 << " " << 1 << "\n";
        //if(cnt > q) cout << "ZA DUZO\n";
        // if(H[x] >= H[x-1] and H[x] >= H[x+1]) cout << "OK\n";
        // else cout << "ZLE\n";
    }
    else if(k == 1 and q <= 3500){

    }
    else{
        srand(time(NULL));
        pair<int,pair<int,pii>> naj = {-1, {-1, {-1, -1}}};
        for(int i = 0; i < q/3; ++i){
            int x = rand() % n + 1;
            int y = rand() % m + 1;
            int z = rand() % k + 1;
            naj = max(naj, {pars(x,y,z), {x, {y, z}}});
        }
        int x = naj.second.first;
        int y = naj.second.second.first;
        int z = naj.second.second.second;
        while(true){
            pair<int,pii> nxt = synowie(x, y, z);
            if(nxt.first == -1) break;
            x = nxt.first;
            y = nxt.second.first;
            z = nxt.second.second;
        }
        cout << "! " << x << " " << y << " " << z << "\n";
    }

    return 0;
}
#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...