結果

問題 No.5001 排他的論理和でランニング
ユーザー ra5anchor
提出日時 2025-04-19 10:24:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,338 ms / 1,500 ms
コード長 2,830 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 81,780 KB
実行使用メモリ 98,432 KB
スコア 52,428,740
最終ジャッジ日時 2025-04-19 10:25:47
合計ジャッジ時間 73,130 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 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

    Sa, Sb, best = hill_climbing_xor(A, M, tk, LIMIT)

    print(*Sa.data)
    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