結果

問題 No.3102 floor sqrt xor
コンテスト
ユーザー LyricalMaestro
提出日時 2025-04-26 03:25:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,091 bytes
コンパイル時間 670 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 66,984 KB
最終ジャッジ日時 2025-04-26 03:25:57
合計ジャッジ時間 4,089 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/3102

import math

def to_2(N):
    array = []
    while N > 0:
        array.append(N % 2)

        N //= 2
    array.reverse()
    return array

def to_2x(N, k):
    array = []
    for _ in range(k + 1):
        array.append(N % 2)

        N //= 2
    array.reverse()
    return array

def sqrt(n):
    low = 0
    high = 2 * int(math.sqrt(n))
    while high - low > 1:
        mid = (high + low) // 2
        if mid ** 2 <= n:
            low = mid
        else:
            high = mid
    if high ** 2 <= n:
        return high
    else:
        return low

def solve(N):
    array = to_2(N)

    if len(array) <= 4:
        for k in range(2 ** len(array)):
            l = sqrt(k)
            if l ^ k == N:
                return k
        return -1
    else:
        k = len(array) - 1
        n0 = 0
        while 2 * k > len(array):
            n0 += (1 << k) * array[len(array) - 1 - k]
            k -= 1

        min_x = 0
        max_x = (1 << (k + 1)) - 1
        min_l = sqrt(n0 + min_x)
        max_l = sqrt(n0 + max_x)

        array_min = to_2x(min_l, k)
        array_max = to_2x(max_l, k)
        k0 = k
        for i in range(k0 + 1):
            if array_max[i] == array_min[i]:
                x = array_max[i]
                y = x ^ array[len(array) - 1 - k]
                n0 += (1 << k) * y
                k -= 1

        if k == -1:
            n1 = sqrt(n0)
            if n1 ^ n0 == N:
                return n0
            return -1

        for bit in range(2 ** (k + 1)):
            n1 = n0 + bit
            n2 = sqrt(n1)
            if n1 ^ n2 == N:
                return n1
        return -1


def solve2(N):
    array = to_2(N)
    for bit in range(2 ** len(array)):
        bit1 = sqrt(bit)
        if bit1 ^ bit == N:
            return bit
    return -1




def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N = int(input())
        ans = solve(N)
        answers.append(ans)

    for ans in answers:
        print(ans)



                


if __name__ == "__main__":
    main()
0