Submission #647547

#TimeUsernameProblemLanguageResultExecution timeMemory
647547fatemetmhrWorm Worries (BOI18_worm)C++17
59 / 100
549 ms27072 KiB
// ~ Be Name Khoda ~

// Harf ke nazanim... 
// Zende bemoonim?
// Ya oonm na?


#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;


 
int n, m, k, q;
map <pair<int, int>, ll> av[maxn5];
pair<int, int> nei[6] = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0), mp(0, 0), mp(0, 0)};
ll ans[7];
int mxx = -1, mxy, mxz;
 
 
inline ll ask(int x, int y, int z){
    if(x < 1 || x > n || y < 1 || y > m || z < 1 || z > k)
        return -1;
    if(av[z].find({x, y}) != av[z].end())
        return av[z][{x, y}];
    cout << "? " << x << ' ' << y << ' ' << z << endl;
    cin >> av[z][{x, y}];
    if(mxx == -1 || av[mxz][mp(mxx, mxy)] < av[z][mp(x, y)])
        mxx = x, mxy = y, mxz = z;
    if(av[z][{x, y}] == -1)
        exit(0);
    return av[z][{x, y}];
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    /*
    long double a = 1153;
    a /= 1154;
    int t = 900;
    while(t--){
        a *= 1153; a /= 1154;
    }

    cout << a << endl;
    return 0;
    */
    
    cin >> n >> m >> k >> q;
    int tt = (k == 1 ? 700 : 30000);
    while(tt--){
        int x = rng() % n + 1, y = rng() % m + 1, z = rng() % k + 1;
        if(av[z].find({x, y}) != av[z].end()){
            tt++;
            continue;
        }
        ask(x, y, z);
    }

    int x = mxx, y = mxy, z = mxz;
    while(true){
        if(k == 1)
            shuffle(nei, nei + 4, rng);
        int mx = 6; ans[6] = av[z][mp(x, y)];
        for(int i = 0; i < 6; i++){
            ans[i] = ask(x + nei[i].fi, y + nei[i].se, z + (i == 4 ? 1 : (i == 5 ? -1 : 0)));
            if(ans[i] > ans[mx]){
                mx = i;
                break;
            }
        }
        if(mx == 6){
            cout << "! " << x << ' ' << y << ' ' << z << endl;
            return 0;
        }
        x += nei[mx].fi;
        y += nei[mx].se;
        z += (mx == 4 ? 1 : (mx == 5 ? -1 : 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...