結果

問題 No.5020 Averaging
ユーザー Ang1077Ang1077
提出日時 2024-02-25 16:36:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 839 ms / 1,000 ms
コード長 4,733 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 83,400 KB
スコア 27,778,448
最終ジャッジ日時 2024-02-25 16:36:42
合計ジャッジ時間 29,436 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 587 ms
82,632 KB
testcase_01 AC 839 ms
81,864 KB
testcase_02 AC 400 ms
82,632 KB
testcase_03 AC 407 ms
81,864 KB
testcase_04 AC 416 ms
82,120 KB
testcase_05 AC 661 ms
82,760 KB
testcase_06 AC 561 ms
82,376 KB
testcase_07 AC 385 ms
82,376 KB
testcase_08 AC 535 ms
82,376 KB
testcase_09 AC 423 ms
82,248 KB
testcase_10 AC 563 ms
81,864 KB
testcase_11 AC 532 ms
82,248 KB
testcase_12 AC 418 ms
82,504 KB
testcase_13 AC 542 ms
82,248 KB
testcase_14 AC 667 ms
82,248 KB
testcase_15 AC 779 ms
82,632 KB
testcase_16 AC 494 ms
82,888 KB
testcase_17 AC 483 ms
82,248 KB
testcase_18 AC 659 ms
83,016 KB
testcase_19 AC 608 ms
82,888 KB
testcase_20 AC 457 ms
82,248 KB
testcase_21 AC 741 ms
82,632 KB
testcase_22 AC 537 ms
82,120 KB
testcase_23 AC 589 ms
82,760 KB
testcase_24 AC 500 ms
82,376 KB
testcase_25 AC 400 ms
82,376 KB
testcase_26 AC 599 ms
82,760 KB
testcase_27 AC 417 ms
82,376 KB
testcase_28 AC 811 ms
82,632 KB
testcase_29 AC 693 ms
83,400 KB
testcase_30 AC 487 ms
82,376 KB
testcase_31 AC 689 ms
82,504 KB
testcase_32 AC 558 ms
83,400 KB
testcase_33 AC 350 ms
81,864 KB
testcase_34 AC 422 ms
82,760 KB
testcase_35 AC 548 ms
82,376 KB
testcase_36 AC 423 ms
82,248 KB
testcase_37 AC 502 ms
81,864 KB
testcase_38 AC 591 ms
82,632 KB
testcase_39 AC 437 ms
82,248 KB
testcase_40 AC 334 ms
81,864 KB
testcase_41 AC 493 ms
82,504 KB
testcase_42 AC 543 ms
82,248 KB
testcase_43 AC 348 ms
82,120 KB
testcase_44 AC 571 ms
82,888 KB
testcase_45 AC 393 ms
81,864 KB
testcase_46 AC 612 ms
82,504 KB
testcase_47 AC 546 ms
83,016 KB
testcase_48 AC 453 ms
82,248 KB
testcase_49 AC 652 ms
82,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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, A_list, B_list
    St = 5 * 10**17
    N = II()
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = MII()
    A_list = A[:]
    B_list = B[:]

    A = tuple(A)
    B = tuple(B)


def solve():
    ans = beam()

    A_n, B_n = get_A_B(ans)
    tmp, _ = get_ans(A_n, B_n, ans)
    ans = [(i + 1, j + 1) for i, j in ans]
    # print(len(ans))
    for i in tmp:
        ans.append(i)

    # A_n = A_list[:]
    # B_n = B_list[:]

    # for i, j in ans:
    #     A_n[i - 1], A_n[j - 1] = (A_n[i - 1] + A_n[j - 1]) // 2, (
    #         A_n[i - 1] + A_n[j - 1]
    #     ) // 2
    #     B_n[i - 1], B_n[j - 1] = (B_n[i - 1] + B_n[j - 1]) // 2, (
    #         B_n[i - 1] + B_n[j - 1]
    #     ) // 2
    #     print(max(abs(St - A_n[0]) // 1000000, abs(St - B_n[0]) // 1000000))

    return ans


def get_A_B(ans):
    A_n = A_list[:]
    B_n = B_list[:]
    # print(ans)
    for i, j in ans:
        A_n[i], A_n[j] = A_n[i] // 2 + A_n[j] // 2, A_n[i] // 2 + A_n[j] // 2
        B_n[i], B_n[j] = B_n[i] // 2 + B_n[j] // 2, B_n[i] // 2 + B_n[j] // 2
    return A_n, B_n


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


def beam():
    depth = 10
    width = 10
    heap = []
    heap.append((max(abs(St - A[0]), abs(St - B[0])), []))

    heap = sorted(heap, key=lambda x: x[0])[:width]
    ans = []
    for _ in range(depth):
        new_heap = []
        while heap:
            score, ans = heap.pop()
            A_n, B_n = get_A_B(ans)
            for i in range(0, 45):
                for j in range(i + 1, 45):
                    if A_n[i] == A_n[j] and B_n[i] == B_n[j]:
                        continue
                    ans_n = ans[:]
                    ans_n.append((i, j))
                    A_nn, B_nn = A_n[:], B_n[:]
                    A_nn[i], A_nn[j] = (
                        A_nn[i] // 2 + A_nn[j] // 2,
                        A_nn[i] // 2 + A_nn[j] // 2,
                    )
                    B_nn[i], B_nn[j] = (
                        B_nn[i] // 2 + B_nn[j] // 2,
                        B_nn[i] // 2 + B_nn[j] // 2,
                    )

                    _, tmp = get_ans(A_nn, B_nn, ans_n)

                    if tmp < score:
                        new_heap.append((tmp, ans_n))
        if len(new_heap) == 0:
            break

        heap = sorted(new_heap, key=lambda x: x[0])[:width]
        # print(heap)
        _, ans = heap[0]

    return ans


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


def main():
    Input()
    Output(solve())
    # Output([])


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