Submission #648384

#	Time	Username	Problem	Language	Result	Execution time	Memory
648384		fatemetmhr	Worm Worries (BOI18_worm)	C++17	59 / 100	555 ms	27064 KiB

worm

// ~ 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;
typedef long double ld;

#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 ld  grt   =  (sqrt(5) - 1) / (2.0);
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 = 1, int z = 1){
    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;

    if(m == 1){
        int l = 1, r = n;
        if(ask(l) >= ask(l + 1))
            return cout << "! " << 1 << ' ' << 1 << ' ' << 1 << endl, 0;
        if(ask(r) >= ask(r - 1))
            return cout << "! " << n << ' ' << 1 << ' ' << 1 << endl, 0;
        int x2 = grt * n + 1, x1 = n - grt * n;
        while(r - l + 1 > 3){
            //cout << "here " << l << ' ' << r << ' ' << x1 << ' '<< x2 << endl;
            if(x1 == l || x2 == r || x1 == x2)
                break;
            if(ask(x1) < ask(x2)){
                l = x1;
                x1 = x2;
                x2 = l + grt * (r - l);
            }
            else{
                r = x2;
                x2 = x1;
                x1 = r - grt * (r - l);
            }
        }

        int mx = l + 1;
        for(int i = l + 2; i < r; i++) if(ask(i) > ask(mx))
            mx = i;
        cout << "! " << mx << ' ' << 1 << ' ' << 1 << endl;
        return 0;
    }


    int tt = (k == 1 ? 1000 : 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));
    }

}

// 169 4525 3593 260 4064 9309 8254 5396 6444 7211 || 4197 8073 9967 6637 8443 1940 7008 7999 9147 6986

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