結果

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

ソースコード

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,C-1,-1):
        if R & (1<<i)==0:
            ind=i
            break

    #print(ind)

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

    j=1<<ind
    r=(R-j)//(j*2)
    xx=r*(j*2)+j-(j*2)
    while xx<R:
        xx+=j*2

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

    #(1<<ind,ind+1)

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

    return ANS+1 + distance(R,C,xx-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