Submission #551711

#	Time	Username	Problem	Language	Result	Execution time	Memory
551711		tranxuanbach	Worm Worries (BOI18_worm)	C++17	81 / 100	476 ms	5060 KiB

worm

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
int randt(int l, int r, int k = 0){
    if (k > 0){
        return max(randt(l, r, k - 1), (int)(rando() % (r - l + 1)) + l);
    }
    if (k < 0){
        return min(randt(l, r, k + 1), (int)(rando() % (r - l + 1)) + l);
    }
    return rando() % (r - l + 1) + l;
}

const int SMALL = 5;

struct point3_t{
    int x, y, z;

    point3_t(): x(0), y(0), z(0){

    }

    point3_t(int x, int y, int z): x(x), y(y), z(z){

    }

    friend bool operator< (const point3_t &lhs, const point3_t &rhs){
        return tie(lhs.x, lhs.y, lhs.z) < tie(rhs.x, rhs.y, rhs.z);
    }
};

int n, m, k, q;

map <point3_t, int> mapquery;

int query(point3_t a){
    if (not (1 <= a.x and a.x <= n and 1 <= a.y and a.y <= m and 1 <= a.z and a.z <= k)){
        return 0;
    }
    if (mapquery.count(a)){
        return mapquery[a];
    }
    q--;
    cout << "? " << a.x << ' ' << a.y << ' ' << a.z << endl;
    int ans; cin >> ans; return (mapquery[a] = ans);
}

int query(int x, int y = 1, int z = 1){
    return query(point3_t(x, y, z));
}

int query_if(point3_t a){
    if (mapquery.count(a)){
        return mapquery[a];
    }
    return 0;
}

int query_if(int x, int y = 1, int z = 1){
    return query_if(point3_t(x, y, z));
}

void answer(point3_t a){
    cout << "! " << a.x << ' ' << a.y << ' ' << a.z << endl;
    #ifdef FEXT
    cout << "Q " << q << endl;
    #endif
    exit(0);
}

void answer(int x, int y = 1, int z = 1){
    answer(point3_t(x, y, z));
}

namespace subtask1{
    bool check(){
        return m == 1 and k == 1;
    }

    ld phi = (sqrtl(5) - 1) / 2;

    void solve(){
        int lo = 1, hi = n;

        int mid1 = (int)round(phi * (hi - lo)) + lo;
        while (lo < hi){
            int mid2 = (lo + hi) - mid1;
            if (mid1 == mid2){
                if (mid2 - 1 >= lo){
                    mid2--;
                }
                else{
                    mid2++;
                }
            }

            if (hi - lo + 1 >= 5 and abs(max(mid1, mid2) - ((int)round(phi * (hi - lo)) + lo)) >= 5){
                mid1 = (int)round(phi * (hi - lo)) + lo;
                mid2 = (lo + hi) - mid1;
            }

            if (query(mid1) > query(mid2)){
                if (mid1 < mid2){
                    hi = min(mid2, hi - 1);
                }
                else{
                    lo = max(mid2, lo + 1);
                }
            }
            else{
                if (mid1 < mid2){
                    lo = max(mid1, lo + 1);
                }
                else{
                    hi = min(mid1, hi - 1);
                }
                mid1 = mid2;
            }
        }
        answer(lo);
    }
}

namespace subtask2{
    bool check(){
        return k == 1;
    }

    void solve(){
        int lox = 1, hix = n, loy = 1, hiy = m;

        while (lox < hix or loy < hiy){
            int lenx = hix - lox + 1, leny = hiy - loy + 1;
            int mid = -1, val1 = 0, val2 = 0, val3 = 0, val4 = 0;
            if (lenx >= leny){
                mid = (lox + hix) >> 1;
                ForE(y, loy, hiy){
                    val1 = max(val1, query_if(lox, y));
                    val2 = max(val2, query_if(hix, y));
                }
                ForE(x, lox, hix){
                    if (x <= mid){
                        val1 = max({val1, query_if(x, loy), query_if(x, hiy)});
                    }
                    else{
                        val2 = max({val2, query_if(x, loy), query_if(x, hiy)});
                    }
                }

                ForE(y, loy, hiy){
                    val3 = max(val3, query(mid, y));
                }
                if (val3 <= max(val1, val2)){
                    if (val1 > val2){
                        hix = mid;
                    }
                    else{
                        lox = mid + 1;
                    }
                    continue;
                }
                ForE(y, loy, hiy){
                    if (query(mid, y) == val3){
                        val4 = max(val4, query(mid + 1, y));
                    }
                }
                if (val3 > val4){
                    hix = mid;
                }
                else{
                    lox = mid + 1;
                }
            }
            else{
                mid = (loy + hiy) >> 1;
                ForE(x, lox, hix){
                    val1 = max(val1, query_if(x, loy));
                    val2 = max(val2, query_if(x, hiy));
                }
                ForE(y, loy, hiy){
                    if (y <= mid){
                        val1 = max({val1, query_if(lox, y), query_if(hix, y)});
                    }
                    else{
                        val2 = max({val2, query_if(lox, y), query_if(hix, y)});
                    }
                }

                ForE(x, lox, hix){
                    val3 = max(val3, query(x, mid));
                }
                if (val3 <= max(val1, val2)){
                    if (val1 > val2){
                        hiy = mid;
                    }
                    else{
                        loy = mid + 1;
                    }
                    continue;
                }
                ForE(x, lox, hix){
                    if (query(x, mid) == val3){
                        val4 = max(val4, query(x, mid + 1));
                    }
                }
                if (val3 > val4){
                    hiy = mid;
                }
                else{
                    loy = mid + 1;
                }
            }
        }
        answer(lox, loy);
    }
}

namespace subtask3{
    bool check(){
        return 1;
    }

    int dx[6] = {-1, 1, 0, 0, 0, 0};
    int dy[6] = {0, 0, -1, 1, 0, 0};
    int dz[6] = {0, 0, 0, 0, -1, 1};

    vi rd = {0, 1, 2, 3, 4, 5};

    void solve(){
        vector <pair <int, point3_t>> a;
        ForE(turn, 1, q / 2){
            int x = randt(1, n), y = randt(1, m), z = randt(1, k);
            a.emplace_back(query(x, y, z), point3_t(x, y, z));
        }
        sort(bend(a));
        point3_t u = a.back().se;
        while (q){
            if (q >= ((k + 9) / 10) * 2000){
                pair <int, point3_t> mx = {-1, point3_t()};
                For(d, 0, 6){
                    point3_t v = point3_t(u.x + dx[d], u.y + dy[d], u.z + dz[d]);
                    mx = max(mx, make_pair(query(v), v));
                }
                if (mx.fi > query(u)){
                    u = mx.se;
                }
                else{
                    answer(u);
                }
            }
            else{
                shuffle(bend(rd), rando);
                bool ck = 1;
                For(i, 0, 6){
                    int d = rd[i];
                    point3_t v = point3_t(u.x + dx[d], u.y + dy[d], u.z + dz[d]);
                    if (q and query(v) > query(u)){
                        u = v;
                        ck = 0;
                        break;
                    }
                }
                if (ck){
                    answer(u);
                }
            }
        }
        answer(u);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m >> k >> q;

    if (subtask1::check()){
        subtask1::solve();
        return 0;
    }
    // if (subtask2::check()){
    //     subtask2::solve();
    //     return 0;
    // }
    if (subtask3::check()){
        subtask3::solve();
        return 0;
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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