Submission #651105

#	Time	Username	Problem	Language	Result	Execution time	Memory
651105		fatemetmhr	Worm Worries (BOI18_worm)	C++17	100 / 100	800 ms	31856 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(0, -1), mp(1, 0), 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}];
}

inline void solve1d(){
    int l = 1, r = n;
    if(ask(l) >= ask(l + 1)){
        cout << "! " << 1 << ' ' << 1 << ' ' << 1 << endl;
        return;
    }
    if(ask(r) >= ask(r - 1)){
        cout << "! " << n << ' ' << 1 << ' ' << 1 << endl;
        return;
    }
    int x2 = n / grt + 1, x1 = n - n / grt;
    while(r - l + 1 >= 3){
        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;
}

inline void solve2d(){
    int xl = 1, xr = n, yl = 1, yr = m;
    int mxx = 1, mxy = 1;
    while(xl < xr || yl < yr){
        if(xr - xl < yr - yl){
            int mid = (yl + yr) >> 1, mx = xl;
            for(int i = xl + 1; i <= xr; i++) 
                if(ask(i, mid) > ask(mx, mid))
                    mx = i;
            int bnei = 5;
            ans[5] = ask(mx, mid);
            for(int i = 0; i < 4; i++){
                ans[i] = ask(mx + nei[i].fi, mid + nei[i].se);
                if(ans[i] > ans[bnei]){
                    bnei = i;
                }
            }
            if(bnei == 5){
                cout << "! " << mx << ' ' << mid << ' ' << 1 << endl;
                return;
            }
            int xb = mx + nei[bnei].fi, yb = mid + nei[bnei].se;
            if(yb == mid || ask(xb, yb) < ask(mxx, mxy)){
                if(mxy < mid)
                    yr = mid - 1;
                else
                    yl = mid + 1;
            }
            else{
                if(yb < mid)
                    yr = mid - 1;
                else
                    yl = mid + 1;
                mxx = xb; mxy = yb;
            }
        }
        else{
            int mid = (xl + xr) >> 1, mx = yl;
            for(int i = yl + 1; i <= yr; i++) 
                if(ask(mid, i) > ask(mid, mx))
                    mx = i;
            int bnei = 5;
            ans[5] = ask(mid, mx);
            for(int i = 0; i < 4; i++){
                ans[i] = ask(mid + nei[i].fi, mx + nei[i].se);
                if(ans[i] > ans[bnei]){
                    bnei = i;
                }
            }
            if(bnei == 5){
                cout << "! " << mid << ' ' << mx << ' '<< 1 << endl;
                return;
            }
            int xb = mid + nei[bnei].fi, yb = mx + nei[bnei].se;
            if(xb == mid || ask(xb, yb) < ask(mxx, mxy)){
                if(mxx < mid)
                    xr = mid - 1;
                else
                    xl = mid + 1;
            }
            else{
                if(xb < mid)
                    xr = mid - 1;
                else
                    xl = mid + 1;
                mxx = xb; mxy = yb;
            }
        }
    }
    cout << "! " << xl << ' ' << yl << ' ' << 1 << endl;
    return;
}

inline void solve3d(){
    int tt = 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){
        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;
        }
        x += nei[mx].fi;
        y += nei[mx].se;
        z += (mx == 4 ? 1 : (mx == 5 ? -1 : 0));
    }
    return;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> k >> q;

    if(m == 1)
        solve1d();
    else if(k == 1)
        solve2d();
    else
        solve3d();
}

/*
5610 6793 6641 2049 2223 1965 2184 4610 6411 3212 
255  4906 6242 3562 8231 8399 7118 8195 8224 1593 
4500 9240 7705 7709 5735 4886 7327 4052 1976 3103 
653  6416 7165 5924 2822 5975 9607 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: 19 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23