Submission #650335

#	Time	Username	Problem	Language	Result	Execution time	Memory
650335		fatemetmhr	Worm Worries (BOI18_worm)	C++17	81 / 100	447 ms	27400 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   =  (1 + sqrt(5)) / (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 = n / grt + 1, x1 = n - n / grt;
        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 + (r - l + 1) / grt;
            }
            else{
                r = x2;
                x2 = x1;
                x1 = r - (r - l + 1) / grt;
            }
        }

        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));
    }

}

/*
5610 6793 6641 2049 2223 1965 2184 4610 6411 3212 
255 4906 6242 3562 8231 1399 7118 8195 8224 1593 
4500 9240 7705 7709 5735 4886 7327 4052 1976 3103 
653 6416 7165 5924 2822 5975 5607 8960 217 1287 
2051 4176 9826 3025 983 4140 1416 8184 8580 3233
*/

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