結果

問題 No.5001 排他的論理和でランニング
ユーザー ra5anchor
提出日時 2025-04-19 14:26:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,288 ms / 1,500 ms
コード長 4,734 bytes
コンパイル時間 510 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 102,040 KB
スコア 52,270,145
最終ジャッジ日時 2025-04-19 14:27:06
合計ジャッジ時間 13,296 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import copy
import random
from time import perf_counter
import argparse
import sys
import math

random.seed(0)

class TimeKeeper:
    def __init__(self):
        self.start_time = perf_counter()
    def is_time_over(self, LIMIT):
        return (perf_counter() - self.start_time) >= LIMIT
    def time_now(self):
        return (perf_counter() - self.start_time)


class XorSet:
    def __init__(self, initial):
        # リスト＋辞書で要素集合を管理し、
        # 定数時間でランダム選択・追加・削除・XOR 更新を行う
        self.data = list(initial)
        self.pos  = {v:i for i,v in enumerate(self.data)}
        self.current_xor = 0
        for v in self.data:
            self.current_xor ^= v

    def __len__(self):
        return len(self.data)

    def random_element(self):
        idx = random.randrange(len(self.data))
        return self.data[idx]

    def remove(self, v):
        idx = self.pos[v]
        last = self.data[-1]
        # スワップして末尾を pop
        self.data[idx] = last
        self.pos[last] = idx
        self.data.pop()
        del self.pos[v]
        # XOR 更新
        self.current_xor ^= v

    def add(self, v):
        self.pos[v] = len(self.data)
        self.data.append(v)
        # XOR 更新
        self.current_xor ^= v

def hill_climbing_xor(values, M, tk, LIMIT):
    # 初期分割
    random.shuffle(values)
    Sa = XorSet(values[:M])
    Sb = XorSet(values[M:])
    best_xor = Sa.current_xor

    loop = 0
    while True:
        loop += 1
        if loop%100==0 and tk.is_time_over(LIMIT):
            break

        # 近傍：A から a_val, Sb から b_val をランダムに選んで交換を試す
        a_val = Sa.random_element()
        b_val = Sb.random_element()

        # 交換後の Sa の XOR を定数時間で計算
        new_xor = Sa.current_xor ^ a_val ^ b_val

        # 改善があれば実際にスワップ
        if new_xor > Sa.current_xor:
            Sa.remove(a_val)
            Sb.remove(b_val)
            Sa.add(b_val)
            Sb.add(a_val)
            best_xor = new_xor
            print(f"best: {loop=} {best_xor=}", file=sys.stderr)

    return Sa, Sb, best_xor


def hill_climbing_xor2(values, M, K, xor_init, tk, LIMIT, perfect=2**20-1):
    # K個少ない
    M = M - K
    # 初期分割
    random.shuffle(values)
    Sa = XorSet(values[:M])
    Sb = XorSet(values[M:])
    Sa.current_xor ^= xor_init
    best_xor = Sa.current_xor

    loop = 0
    while True:
        loop += 1
        if loop%100==0 and tk.is_time_over(LIMIT):
            break
        if loop%100==0 and best_xor >= perfect - (2**K-1):
            break

        # 近傍：A から a_val, Sb から b_val をランダムに選んで交換を試す
        a_val = Sa.random_element()
        b_val = Sb.random_element()

        # 交換後の Sa の XOR を定数時間で計算
        new_xor = Sa.current_xor ^ a_val ^ b_val

        # 改善があれば実際にスワップ
        if new_xor > Sa.current_xor:
            Sa.remove(a_val)
            Sb.remove(b_val)
            Sa.add(b_val)
            Sb.add(a_val)
            best_xor = new_xor
            print(f"best: {loop=} {best_xor=}", file=sys.stderr)

    return Sa, Sb, best_xor



###########################################
def main(DEBUG):
    tk = TimeKeeper()
    LIMIT = 1.2

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # 5 <= N <= 10**5
    # 1 <= M <= N
    # 1 <= Ai <= 10**6
    # Ai != Aj
    # print(M, file=sys.stderr)
    # exit()

        
    A.sort()
    La = []
    Lb = []
    for k in range(10):
        K = k
        found = False
        for i in range(len(A)-1):
            a1 = A[i+1]
            a0 = A[i]
            if a1 - a0 == 2**k:
                # print(k, a0, a1, file=sys.stderr)
                La.append(a0)
                Lb.append(a1)
                A.remove(a0)
                A.remove(a1)
                found = True
                break
        if found == False:
            break
    xor_init = 0
    for i in range(K):
        if La[i] != -1:
            xor_init ^= La[i]

    Sa, Sb, best = hill_climbing_xor2(A, M, K, xor_init, tk, LIMIT)

    ans = Sa.data[:]
    for k in range(K):
        if (best>>k) & 1 == 1:
            ans.append(La[k])
        else:
            ans.append(Lb[k])
            best += (1<<k)

    # print(*Sa.data)
    print(*ans)

    print("SC", best, file=sys.stderr)    
    return
    

if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Debug mode')
    parser.add_argument('--debug', action='store_true', help='Enable debug mode')
    args = parser.parse_args()
    main(args.debug)
0