結果

問題 No.5020 Averaging
コンテスト
ユーザー Ang1077
提出日時 2024-02-25 14:06:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,083 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 371,964 KB
スコア 0
最終ジャッジ日時 2024-02-25 14:06:23
合計ジャッジ時間 4,933 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque, defaultdict
from itertools import (
    accumulate,
    product,
    permutations,
    combinations,
    combinations_with_replacement,
)
import math
from bisect import bisect_left, insort_left, bisect_right, insort_right
from pprint import pprint
from heapq import heapify, heappop, heappush
import string

# 小文字アルファベットのリスト
alph_s = list(string.ascii_lowercase)
# 大文字アルファベットのリスト
alph_l = list(string.ascii_uppercase)

# product : bit全探索 product(range(2),repeat=n)
# permutations : 順列全探索
# combinations : 組み合わせ（重複無し）
# combinations_with_replacement : 組み合わせ（重複可）
# from sortedcontainers import SortedSet, SortedList, SortedDict
sys.setrecursionlimit(10**7)
around4 = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上下左右
around8 = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
inf = float("inf")
mod = 998244353
input = lambda: sys.stdin.readline().rstrip()
P = lambda *x: print(*x)
PY = lambda: print("Yes")
PN = lambda: print("No")
II = lambda: int(input())
MII = lambda: map(int, input().split())
LMII = lambda: list(map(int, input().split()))


def dlist(*l, fill=0):
    if len(l) == 1:
        return [fill] * l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]


# 入力
def Input():
    global N, A, B, St
    St = 5 * 10**17
    N = II()
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = MII()


def solve():
    ans = beam()
    ans = [(i + 1, j + 1) for i, j in ans]
    A_n, B_n = get_A_B(ans)
    tmp = get_ans(A_n, B_n, ans)
    for i in tmp:
        ans.append(i)
    return ans


def get_A_B(ans):
    A_n = A[:]
    B_n = B[:]
    for i, j in ans:
        A_n[i], A_n[j] = (A[i] + A[j]) // 2, (A[i] + A[j]) // 2
        B_n[i], B_n[j] = (B[i] + B[j]) // 2, (B[i] + B[j]) // 2
    return A_n, B_n


def get_ans(A, B, ans_prv):
    ans_list = []
    for _ in range(50 - len(ans_prv)):
        score = abs(St - A[0]) + abs(St - B[0])
        tmp = score
        ans = None
        for j in range(1, 45):
            a, b = (A[0] + A[j]) // 2, (B[0] + B[j]) // 2
            if abs(St - a) + abs(St - b) < tmp:
                tmp = abs(St - a) + abs(St - b)
                ans = j
        if ans:
            ans_list.append([1, ans + 1])
            A[0], A[ans] = (A[0] + A[ans]) // 2, (A[0] + A[ans]) // 2
            B[0], B[ans] = (B[0] + B[ans]) // 2, (B[0] + B[ans]) // 2
        else:
            break
    return ans_list


def beam():
    target_a, target_b = St - (A[0] - St), St - (B[0] - St)
    depth = 40
    width = 100
    heap = []
    for i in range(0, 45):
        for j in range(i + 1, 45):
            a, b = (A[i] + A[j]) // 2, (B[i] + B[j]) // 2
            if i == 0:
                heappush(heap, (abs(St - a) + abs(St - b), [(i, j)]))
            else:
                heappush(heap, (abs(target_a - a) + abs(target_b - b), [(i, j)]))

    for idx in range(depth):
        new_heap = []
        while heap:
            score, ans = heappop(heap)

            A_n, B_n = get_A_B(ans)

            target_a, target_b = St - (A_n[0] - St), St - (B_n[0] - St)

            for i in range(0, 45):
                for j in range(i + 1, 45):
                    a, b = (A_n[i] + A_n[j]) // 2, (B_n[i] + B_n[j]) // 2
                    ans_n = ans[:]
                    ans_n.append((i, j))
                    if i == 0:
                        heappush(new_heap, (abs(St - a) + abs(St - b), ans_n))
                    else:
                        heappush(
                            new_heap, (abs(target_a - a) + abs(target_b - b), ans_n)
                        )
        for _ in range(width):
            heappush(heap, heappop(new_heap))
            if len(new_heap) == 0:
                break
    _, ans = heappop(heap)
    return ans


# 出力
def Output(ans):
    print(len(ans))
    for i in ans:
        print(*i)


def main():
    Input()
    Output(solve())


if __name__ == "__main__":
    main()
0