結果

問題 No.3018 目隠し宝探し
ユーザー Jikky1618
提出日時 2025-01-25 15:44:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,645 bytes
コンパイル時間 3,807 ms
コンパイル使用メモリ 278,276 KB
実行使用メモリ 26,356 KB
平均クエリ数 2.68
最終ジャッジ日時 2025-01-25 23:47:32
合計ジャッジ時間 8,820 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other AC * 5 WA * 2 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

// 離散関数 f: Z -> R の区間 [left, right] での黄金分割探索
template <class T, class F>
auto golden_section_search(ll left, ll right, F&& f, bool maximize = true) {
    ll a = left - 1, x, b;
    {
        ll s = 1, t = 2;
        while (t < right - left + 2) swap(s += t, t);
        x = a + t - s, b = a + t;
    }
    T fx = f(x);
    while (a + b != 2 * x) {
        ll y = a + b - x;
        T fy = f(y);
        if (right < y || maximize ? fx < fy : fx > fy) {
            a = x, x = y, fx = fy;
        } else {
            b = a, a = y;
        }
    }
    return make_pair(x, fx);
}

// N は平方数, 0 <= N <= 4.5*10^18 < 2^62
ll integer_sqrt(ll N) {
    // √N < 2^31
    ll low = -1, high = 1LL << 31;
    while (high - low > 1) {
        ll mid = (low + high) / 2, mid2 = mid * mid;
        if (mid2 <= N) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int H, W;
    cin >> H >> W;
    // int local_ans_h = 17, local_ans_w = 334;
    vector<int> D(1001, -1);

    if (H < W) {
        // H を特定
        auto check = [&](int h, int w) -> int {
            if (h < 1 || h > H) return 1e9;
            if (D[h] != -1) return D[h];
            cout << "? " << h << " " << w << endl;
            // int d = (local_ans_h - h) * (local_ans_h - h) + (local_ans_w - w) * (local_ans_w - w);
            int d;
            cin >> d;
            if (d == -1) assert(false);
            return D[h] = d;
        };
        auto f1 = [&](int h) -> int { return check(h, 1); };

        auto [h, d] = golden_section_search<int>(1, H, f1, false);
        int w = integer_sqrt(d) + 1;

        cout << "! " << h << " " << w << endl;
    } else {
        // W を特定
        auto check = [&](int h, int w) -> int {
            if (w < 1 || w > W) return 1e9;
            if (D[w] != -1) return D[w];
            cout << "? " << h << " " << w << endl;
            // int d = (local_ans_h - h) * (local_ans_h - h) + (local_ans_w - w) * (local_ans_w - w);
            int d;
            cin >> d;
            debug(h, w, d);
            if (d == -1) assert(false);
            return D[w] = d;
        };
        auto f2 = [&](int w) -> int { return check(1, w); };

        auto [w, d] = golden_section_search<int>(1, W, f2, false);
        int h = integer_sqrt(d) + 1;

        cout << "! " << h << " " << w << endl;
    }
}
0