結果

問題 No.2977 Kth Xor Pair
ユーザー titiatitia
提出日時 2024-12-15 04:51:18
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,102 bytes
コンパイル時間 817 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 752,328 KB
最終ジャッジ日時 2024-12-15 04:52:55
合計ジャッジ時間 91,320 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
59,436 KB
testcase_01 AC 37 ms
64,128 KB
testcase_02 AC 141 ms
86,112 KB
testcase_03 AC 114 ms
83,712 KB
testcase_04 AC 115 ms
86,216 KB
testcase_05 AC 121 ms
84,096 KB
testcase_06 AC 118 ms
85,776 KB
testcase_07 MLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 WA -
testcase_26 TLE -
testcase_27 AC 2,643 ms
155,556 KB
testcase_28 AC 1,371 ms
155,500 KB
testcase_29 AC 1,686 ms
155,756 KB
testcase_30 AC 2,597 ms
155,528 KB
testcase_31 AC 2,020 ms
155,124 KB
testcase_32 AC 1,412 ms
113,080 KB
testcase_33 AC 1,259 ms
112,600 KB
testcase_34 AC 1,543 ms
112,988 KB
testcase_35 AC 1,350 ms
113,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

# Trie木

Next_node_id0=[-1]
Next_node_id1=[-1]
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==0:
        
            if Next_node_id0[NOW]==-1: # Nodeを追加する場合
                Next_node_id0[NOW]=Nodes_id

                Next_node_id0.append(-1)
                Next_node_id1.append(-1)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)

                NOW=Nodes_id         
                Nodes_id+=1

            else: # 追加しない場合
                NOW=Next_node_id0[NOW]
        else:
            if Next_node_id1[NOW]==-1: # Nodeを追加する場合
                Next_node_id1[NOW]=Nodes_id

                Next_node_id0.append(-1)
                Next_node_id1.append(-1)
                Parent_id.append(NOW)
                Depth.append(Depth[NOW]+1)
                Count.append(0)

                NOW=Nodes_id         
                Nodes_id+=1

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

    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:
        if count//2>=r:
            break
        now=0
        count2=0
        flag=0
        for dep in range(30,-1,-1):
            
            x,y=Next_node_id0[now],Next_node_id1[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