結果

問題 No.3375 Binary Grid
コンテスト
ユーザー titia
提出日時 2025-11-22 04:42:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,837 bytes
コンパイル時間 552 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 82,296 KB
最終ジャッジ日時 2025-11-22 04:42:21
合計ジャッジ時間 4,223 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 1 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

def distance(R,C,x,y):
    #print(R,C,x,y)
    if R==x and C==y:
        return 0

    ind=-1

    for i in range(y-1,0,-1):
        if R & (1<<i)==0:
            ind=i
            break

    if ind==-1 or (R>=(1<<ind)):
        return max(abs(x-R),abs(y-C))

    #(1<<ind,ind+1)

    ANS=max(x-(1<<ind),y-(ind+1))

    return ANS+1 + distance(R,C,(1<<ind)-1,ind)

    

    
    

def calc(b,R,C,com):
    #print(b,R,C,com)
    if com==0:
        if b==1:
            return 0
        if b==2:
            if R==0 and C==2:
                return 0
            else:
                return 1

        if C==b:
            return R
        mid=2**(b-2)

        if R>=mid:
            if C==b-1:
                return R
            else:
                return mid+calc(b-1,R-mid,C,0)
        else:
            return mid +1+ distance(R,C,mid-1,b-2)
    else:
        if b==3:
            if R==1:
                return 3
            if R==2:
                return 2
            if R==3:
                if C==1:
                    return 2
                else:
                    return 1
        if b==2:
            return 1
        mid=2**(b-2)

        if R>=mid:
            #print("!",b-C,2**(b-1)-R)
            return 1+ calc(b-1,R-mid,C,1)
        else:
            return 2**(b-2) + calc(b-1,R,C,1)
        
    return 0
    


T=int(input())

for tests in range(T):
    R,C=map(int,input().split())

    b=R.bit_length()

    if C==b:
        print(R-1)
        continue

    #print(b)
    M=2**b-1
    m=2**(b-1)

    mid=(m+M+1)//2

    if R>=mid and C==b-1:
        print(R-1)
        continue

    #print(m,M,mid)
    #print(b,R-m,C,0)

    ANS=m-1
    ANS+=calc(b,R-m,C,0)

    print(ANS)
0