結果

問題 No.2493 K-th in L2 with L1
ユーザー InTheBloomInTheBloom
提出日時 2023-10-06 21:46:53
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 1,889 bytes
コンパイル時間 3,747 ms
コンパイル使用メモリ 168,688 KB
実行使用メモリ 4,804 KB
最終ジャッジ日時 2023-10-06 21:46:57
合計ジャッジ時間 2,471 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 10 ms
4,556 KB
testcase_02 AC 11 ms
4,804 KB
testcase_03 AC 10 ms
4,572 KB
testcase_04 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int Q = readln.chomp.to!int;
    foreach (_; 0..Q) {
        int D, K; readln.read(D, K);
        solve(D, K);
    }
}

void solve (int D, int K) {
    // マンハッタン距離Dの点集合を列挙
    alias coord = Tuple!(int, "y", int, "x");
    bool[coord] DistanceDPoints;
    for (int i = 0; i <= D; i++) {
        int y = D-i;
        int x = i;
        DistanceDPoints[coord(y, x)] = true;
        DistanceDPoints[coord(y, -x)] = true;
        DistanceDPoints[coord(-y, x)] = true;
        DistanceDPoints[coord(-y, -x)] = true;
    }

    int[] dist;
    foreach (key, val; DistanceDPoints) {
        dist ~= key.y^^2 + key.x^^2;
    }

    dist.sort;

    // 二分探索
    int f (int idx) {
        if (idx < 0) return -int.max;
        if (dist.length <= idx) return int.max;
        return dist[idx];
    }

    foreach (key, val; DistanceDPoints) {
        int EuclidDist = key.y^^2 + key.x^^2;
        {
            int ok = 0, ng = cast(int) dist.length;
            while (1 < abs(ok-ng)) {
                int mid = (ok+ng) / 2;
                if (f(mid) <= EuclidDist) { 
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
            if (ok+1 < K) continue;
        }
        {
            int ok = -1, ng = cast(int) dist.length;
            while (1 < abs(ok-ng)) {
                int mid = (ok+ng) / 2;
                if (f(mid) < EuclidDist) { 
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
            if (K <= ok+1) continue;
        }

        writeln("Yes");
        writeln(key.x, " ", key.y);
        return;
    }

    writeln("No");
}

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