Submission #648038

#	Time	Username	Problem	Language	Result	Execution time	Memory
648038		fatemetmhr	Worm Worries (BOI18_worm)	C++17	59 / 100	665 ms	27644 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;

#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 = 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; 
        while(r - l > 1){
            int mid = (r + l) >> 1;
            if(r - l > 10){
                if(rng()%2)
                    mid += rng() % 4;
                else
                    mid -= rng() % 4;
            }
            if(rng()%2){
                if(ask(mid) <= ask(l)){
                    r = mid;
                    continue;
                }
                if(ask(mid) <= ask(r)){
                    l = mid;
                    continue;
                }
            }
            else{
                if(ask(mid) <= ask(r)){
                    l = mid;
                    continue;
                }
                if(ask(mid) <= ask(l)){
                    r = mid;
                    continue;
                }
            }
            if(ask(mid - 1) <= ask(mid))
                l = mid;
            else
                r = mid - 1;
        }
        if(l == r)
            cout << "! " << l << ' ' << 1 << ' ' << 1 << endl;
        else{
            if(ask(l) < ask(r))
                swap(l, r);
            cout << "! " << l << ' ' << 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));
    }

}

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