結果

問題 No.3018 目隠し宝探し
コンテスト
ユーザー InTheBloom
提出日時 2025-01-31 20:38:12
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 85 ms / 2,000 ms
コード長 1,685 bytes
コンパイル時間 2,210 ms
コンパイル使用メモリ 196,616 KB
実行使用メモリ 26,240 KB
平均クエリ数 2.64
最終ジャッジ日時 2025-01-31 20:38:19
合計ジャッジ時間 5,841 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int H, W; readln.read(H, W);
    // 2乗のコストというのが大事で、実は広くてもクエリ3回でできる。
    // -> 式展開をすると積に分離できて、2回でできる。(ヤバいね)

    int ask (int i, int j) {
        writefln("? %s %s", i, j);
        stdout.flush;
        int res = readln.chomp.to!int;
        enforce(0 <= res);
        return res;
    }

    void ans (int i, int j) {
        writefln("! %s %s", i, j);
    }

    if (H == 1 && W == 1) {
        ans(H, W);
        return;
    }
    if (H == 1) {
        int u = ask(1, 1);
        u--;

        foreach (i; -1 .. W + 1) {
            if (u == i * (i + 2)) {
                ans(1, i + 2);
                return;
            }
        }
        return;
    }
    if (W == 1) {
        int u = ask(1, 1);
        u--;

        foreach (i; -1 .. H + 1) {
            if (u == i * (i + 2)) {
                ans(i + 2, 1);
                return;
            }
        }

        return;
    }

    int p = ask(1, 1);
    if (p == 0) {
        ans(1, 1);
        return;
    }

    int q = ask(2, 1);
    if (q == 0) {
        ans(0, 0);
        return;
    }

    // h特定 -> w特定とすればクエリ2回
    int h = -(q - p - 2 - 1) / 2;

    int w;
    int iscore = (h - 1) * (h - 1);
    foreach (i; 1 .. W + 1) {
        if (p - iscore - 1 == i * (i + 2)) {
            w = i + 2;
            break;
        }
    }

    ans(h, w);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0