結果

問題 No.3018 目隠し宝探し
コンテスト
ユーザー Jikky1618
提出日時 2025-01-25 15:12:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,616 bytes
コンパイル時間 2,680 ms
コンパイル使用メモリ 275,752 KB
実行使用メモリ 26,096 KB
平均クエリ数 1.00
最終ジャッジ日時 2025-01-25 23:42:08
合計ジャッジ時間 8,166 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

// 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;

    bool is_swap = false;
    if (H > W) swap(H, W), is_swap = true;

    // まず H を特定
    // int local_h = 114, local_w = 514;
    vector<int> res(H + 1, -1);
    auto check = [&](int h) -> int {
        if (res[h] != -1) return res[h];
        if (is_swap) {
            cout << 1 << " " << h << endl;
        } else {
            cout << h << " " << 1 << endl;
        }
        // int d = (local_h - h) * (local_h - h) + (local_w - 1) * (local_w - 1);
        int d;
        cin >> d;
        if (d == -1) assert(false);
        return res[h] = d;
    };

    int left = 0, right = H + 1;
    // 三分探索
    while (right - left > 2) {
        int m1 = left + (right - left) / 3;
        int m2 = right - (right - left) / 3;
        if (check(m1) > check(m2)) {
            left = m1;
        } else {
            right = m2;
        }
    }

    int h = left + 1, d = check(left + 1);
    int w = integer_sqrt(d) + 1;
    if (is_swap) swap(h, w);
    cout << "! " << h << " " << w << endl;
}
0