Submission #1305395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305395		otarius	Worm Worries (BOI18_worm)	C++20	100 / 100	383 ms	4300 KiB

worm

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
// const int maxN;

int n, m, k, q;
const double phi = (3 - sqrt(5.0)) / 2;
int ask(int i, int j, int l) {
    if (i < 1 || i > n || j < 1 || j > m || l < 1 || l > k) return 0;
    cout << "? " << i << ' ' << j << ' ' << l << endl; q--;
    int x; cin >> x; return x;
}
void go1() {
    int l = 1, r = n, m1, m2, arr[n + 1]{};
    m1 = 1 + floor(n * phi); m2 = n - floor(n * phi);
    while (r - l >= 5) {
        if (arr[m1] == 0) arr[m1] = ask(m1, 1, 1);
        if (arr[m2] == 0) arr[m2] = ask(m2, 1, 1);
        
        if (arr[m1] < arr[m2]) {
            l = m1; m1 = m2; m2 = r - floor((r - l + 1) * phi);
        } else {
            r = m2; m2 = m1; m1 = l + floor((r - l + 1) * phi);
        }
    }
    
    int mx = l;
    for (int i = l; i <= r; i++) {
        if (arr[i] == 0) arr[i] = ask(i, 1, 1);
        if (arr[i] > arr[mx]) mx = i;
    }
    
    cout << "! " << mx << " 1 1" << endl;
}
void go2() {
    int mxi = 1, mxj = 1, arr[n + 5][m + 5]{};
    arr[mxi][mxj] = ask(mxi, mxj, 1);
    
    int l1 = 1, r1 = n, l2 = 1, r2 = m;
    while (r1 - l1 > 3 || r2 - l2 > 3) {
        if (r1 - l1 > r2 - l2) {
            int mid = (l1 + r1) / 2, mx = l2;
            for (int i = l2; i <= r2; i++) {
                if (arr[mid][i] == 0) arr[mid][i] = ask(mid, i, 1);
                if (arr[mid][i] > arr[mid][mx]) mx = i;
            }
            
            if (arr[mid][mx] < arr[mxi][mxj]) {
                if (mid < mxi) l1 = mid + 1; else r1 = mid - 1; continue;
            }
            
            mxi = mid; mxj = mx;
            if (arr[mxi - 1][mxj] == 0) arr[mxi - 1][mxj] = ask(mxi - 1, mxj, 1);
            if (arr[mxi + 1][mxj] == 0) arr[mxi + 1][mxj] = ask(mxi + 1, mxj, 1);
            
            if (arr[mxi][mxj] > arr[mxi - 1][mxj] && arr[mxi][mxj] > arr[mxi + 1][mxj]) {
                cout << "! " << mxi << ' ' << mxj << ' ' << 1 << endl; return;
            }
            
            if (arr[mxi - 1][mxj] > arr[mxi + 1][mxj]) r1 = mid;
            else l1 = mid;
        } else {
            int mid = (l2 + r2) / 2, mx = l1;
            for (int i = l1; i <= r1; i++) {
                if (arr[i][mid] == 0) arr[i][mid] = ask(i, mid, 1);
                if (arr[i][mid] > arr[mx][mid]) mx = i;
            }
            
            if (arr[mx][mid] < arr[mxi][mxj]) {
                if (mid < mxj) l2 = mid + 1; else r2 = mid - 1; continue;
            }
            
            mxi = mx; mxj = mid;
            if (arr[mxi][mxj - 1] == 0) arr[mxi][mxj - 1] = ask(mxi, mxj - 1, 1);
            if (arr[mxi][mxj + 1] == 0) arr[mxi][mxj + 1] = ask(mxi, mxj + 1, 1);
            
            if (arr[mxi][mxj] > arr[mxi][mxj - 1] && arr[mxi][mxj] > arr[mxi][mxj + 1]) {
                cout << "! " << mxi << ' ' << mxj << ' ' << 1 << endl; return;
            }
            
            if (arr[mxi][mxj - 1] > arr[mxi][mxj + 1]) r2 = mid;
            else l2 = mid;
        }
    }
    
    for (int i = l1; i <= r1; i++) {
        for (int j = l2; j <= r2; j++) {
            if (arr[i][j] == 0) arr[i][j] = ask(i, j, 1);
            if (arr[i - 1][j] == 0) arr[i - 1][j] = ask(i - 1, j, 1);
            if (arr[i + 1][j] == 0) arr[i + 1][j] = ask(i + 1, j, 1);
            if (arr[i][j - 1] == 0) arr[i][j - 1] = ask(i, j - 1, 1);
            if (arr[i][j + 1] == 0) arr[i][j + 1] = ask(i, j + 1, 1);
            if (arr[i][j] >= arr[i - 1][j] && arr[i][j] >= arr[i + 1][j] && arr[i][j] >= arr[i][j - 1] && arr[i][j] >= arr[i][j + 1]) {
                cout << "! " << i << ' ' << j << ' ' << 1 << endl; return;
            }
        }
    }
    
    cout << "! " << mxi << ' ' << mxj << ' ' << 1 << endl;
}
void go3() {
    int bar = q / 2, cur;
    pair<pii, pii> mx = {{-1, -1}, {-1, -1}};
    while (q > bar) {
        int x = rng() % n + 1, y = rng() % m + 1, z = rng() % k + 1;
        cur = ask(x, y, z);
        
        if (cur > mx.ff.ff) {
            mx.ff.ff = cur; mx.ff.sc = x; mx.sc.ff = y; mx.sc.sc = z;
        }
    }
    
    while (q) {
        cur = ask(mx.ff.sc - 1, mx.sc.ff, mx.sc.sc);
        if (cur > mx.ff.ff) { mx.ff.ff = cur; mx.ff.sc--; }
        if (!q) break;
        
        cur = ask(mx.ff.sc, mx.sc.ff - 1, mx.sc.sc);
        if (cur > mx.ff.ff) { mx.ff.ff = cur; mx.sc.ff--; }
        if (!q) break;
        
        cur = ask(mx.ff.sc, mx.sc.ff, mx.sc.sc - 1);
        if (cur > mx.ff.ff) { mx.ff.ff = cur; mx.sc.sc--; }
        if (!q) break;
        
        cur = ask(mx.ff.sc + 1, mx.sc.ff, mx.sc.sc);
        if (cur > mx.ff.ff) { mx.ff.ff = cur; mx.ff.sc++; }
        if (!q) break;
        
        cur = ask(mx.ff.sc, mx.sc.ff + 1, mx.sc.sc);
        if (cur > mx.ff.ff) { mx.ff.ff = cur; mx.sc.ff++; }
        if (!q) break;
        
        cur = ask(mx.ff.sc, mx.sc.ff, mx.sc.sc + 1);
        if (cur > mx.ff.ff) { mx.ff.ff = cur; mx.sc.sc++; }
        if (!q) break;
    }
    
    cout << "! " << mx.ff.sc << ' ' << mx.sc.ff << ' ' << mx.sc.sc << endl;
}
void solve() {
    cin >> n >> m >> k >> q;
    if (m == 1 && k == 1) go1();
    else if (k == 1) go2();
    else go3();
}
int32_t main() { 
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

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