結果

問題 No.2977 Kth Xor Pair
ユーザー titiatitia
提出日時 2024-12-15 04:43:07
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,501 bytes
コンパイル時間 558 ms
コンパイル使用メモリ 82,132 KB
実行使用メモリ 737,160 KB
最終ジャッジ日時 2024-12-15 04:45:00
合計ジャッジ時間 108,348 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
60,084 KB
testcase_01 AC 37 ms
480,764 KB
testcase_02 MLE -
testcase_03 AC 141 ms
87,160 KB
testcase_04 AC 114 ms
86,956 KB
testcase_05 MLE -
testcase_06 AC 129 ms
86,952 KB
testcase_07 MLE -
testcase_08 TLE -
testcase_09 MLE -
testcase_10 TLE -
testcase_11 MLE -
testcase_12 TLE -
testcase_13 MLE -
testcase_14 TLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 TLE -
testcase_28 AC 1,782 ms
138,388 KB
testcase_29 AC 2,200 ms
141,484 KB
testcase_30 TLE -
testcase_31 AC 2,896 ms
141,488 KB
testcase_32 AC 1,446 ms
113,064 KB
testcase_33 AC 1,632 ms
113,316 KB
testcase_34 AC 1,659 ms
113,568 KB
testcase_35 AC 1,583 ms
254,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,K=map(int,input().split())
A=list(map(int,input().split()))

r=N*(N-1)//2-K+1

# Trie木

Next_node_id=[[-1]*2]
Parent_id=[-1] # 親ノード
Depth=[0] # Trieのノードの深さ
Count=[0] # Trieのノードの重複度

LAST=[]

Nodes_id=1 # 以下、標準入力で与えられたN個の文字列を追加する実装
for i in range(N):
    a=A[i]
    NOW=0
    for i in range(30,-1,-1):
        if a & (1<<i) == 0:
            NEXT=0
        else:
            NEXT=1
        
        if Next_node_id[NOW][NEXT]==-1: # Nodeを追加する場合
            Next_node_id[NOW][NEXT]=Nodes_id

            Next_node_id.append([-1]*2)
            Parent_id.append(NOW)
            Depth.append(Depth[NOW]+1)
            Count.append(0)

            NOW=Nodes_id         
            Nodes_id+=1

        else: # 追加しない場合
            NOW=Next_node_id[NOW][NEXT]

    Count[NOW]+=1 # 終端に印を付ける
    LAST.append(NOW)

Count2=[0]*len(Count)

for x in LAST:
    while x!=-1:
        Count2[x]+=1
        x=Parent_id[x]

OK=0
NG=max(A)+1

# OK以上のものがr個あればOK

while NG>OK+1:
    mid=(OK+NG)//2
    count=0

    for a in A:
        now=0
        count2=0
        flag=0
        for dep in range(30,-1,-1):
            
            x,y=Next_node_id[now]

            #print(now,x,y,Count2[x],Count2[y],count2)
            
            if ((1<<dep) & a == 0) and ((1<<dep) & mid == 0):
                if y!=-1:
                    count2+=Count2[y]

                if x!=-1:
                    now=x
                else:
                    flag=1
                    break

            elif ((1<<dep) & a == 0) and ((1<<dep) & mid != 0):
                if y!=-1:
                    now=y
                else:
                    flag=1
                    break
            elif ((1<<dep) & a != 0) and ((1<<dep) & mid == 0):
                if x!=-1:
                    count2+=Count2[x]

                if y!=-1:
                    now=y
                else:
                    flag=1
                    break
            else:
                if x!=-1:
                    now=x
                else:
                    flag=1
                    break

        #print(count2,now,flag)

        if flag==0:
            count2+=Count2[now]

        #print(a,"^x",">=",mid,"を満たすxをcount",count2)
        count+=count2

    #print(count)

    if count//2>=r:
        OK=mid
    else:
        NG=mid

print(OK)
0