結果

問題 No.2977 Kth Xor Pair
ユーザー titiatitia
提出日時 2024-12-15 04:50:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,091 bytes
コンパイル時間 969 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 649,552 KB
最終ジャッジ日時 2024-12-15 04:52:04
合計ジャッジ時間 98,778 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
59,584 KB
testcase_01 AC 41 ms
449,940 KB
testcase_02 AC 131 ms
85,384 KB
testcase_03 AC 125 ms
85,784 KB
testcase_04 AC 125 ms
85,372 KB
testcase_05 AC 122 ms
457,584 KB
testcase_06 AC 121 ms
85,824 KB
testcase_07 MLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 WA -
testcase_15 TLE -
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 TLE -
testcase_26 TLE -
testcase_27 AC 2,766 ms
155,816 KB
testcase_28 AC 1,549 ms
155,164 KB
testcase_29 AC 1,698 ms
155,424 KB
testcase_30 AC 2,628 ms
155,448 KB
testcase_31 AC 2,144 ms
155,708 KB
testcase_32 AC 1,552 ms
113,340 KB
testcase_33 AC 1,651 ms
112,800 KB
testcase_34 AC 1,876 ms
113,208 KB
testcase_35 AC 1,558 ms
492,840 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:
        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