#955576 (PyPy3) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	uuuus17
提出日時	2024-02-25 16:07:56
言語	PyPy3 (7.3.15)
結果	AC
実行時間	882 ms / 1,000 ms
コード長	5,096 bytes
コンパイル時間	283 ms
コンパイル使用メモリ	81,828 KB
実行使用メモリ	187,356 KB
スコア	22,680,268
最終ジャッジ日時	2024-02-25 16:08:50
合計ジャッジ時間	46,455 ms
ジャッジサーバーID （参考情報）	judge11 / judge10
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	864 ms 138,272 KB
testcase_01	AC	859 ms 154,180 KB
testcase_02	AC	865 ms 165,916 KB
testcase_03	AC	875 ms 133,980 KB
testcase_04	AC	859 ms 135,008 KB
testcase_05	AC	858 ms 111,708 KB
testcase_06	AC	864 ms 106,608 KB
testcase_07	AC	857 ms 134,172 KB
testcase_08	AC	862 ms 187,356 KB
testcase_09	AC	857 ms 136,048 KB
testcase_10	AC	859 ms 125,360 KB
testcase_11	AC	866 ms 142,792 KB
testcase_12	AC	861 ms 140,372 KB
testcase_13	AC	858 ms 131,280 KB
testcase_14	AC	858 ms 133,724 KB
testcase_15	AC	864 ms 142,940 KB
testcase_16	AC	858 ms 133,860 KB
testcase_17	AC	882 ms 139,552 KB
testcase_18	AC	864 ms 146,028 KB
testcase_19	AC	859 ms 130,160 KB
testcase_20	AC	864 ms 136,272 KB
testcase_21	AC	859 ms 152,472 KB
testcase_22	AC	857 ms 123,068 KB
testcase_23	AC	860 ms 129,244 KB
testcase_24	AC	863 ms 144,092 KB
testcase_25	AC	867 ms 175,016 KB
testcase_26	AC	867 ms 141,332 KB
testcase_27	AC	870 ms 143,484 KB
testcase_28	AC	859 ms 131,528 KB
testcase_29	AC	863 ms 121,368 KB
testcase_30	AC	857 ms 129,660 KB
testcase_31	AC	865 ms 130,648 KB
testcase_32	AC	873 ms 177,808 KB
testcase_33	AC	862 ms 155,596 KB
testcase_34	AC	861 ms 124,392 KB
testcase_35	AC	861 ms 136,876 KB
testcase_36	AC	860 ms 136,536 KB
testcase_37	AC	866 ms 131,800 KB
testcase_38	AC	859 ms 135,916 KB
testcase_39	AC	861 ms 131,804 KB
testcase_40	AC	858 ms 136,248 KB
testcase_41	AC	863 ms 138,096 KB
testcase_42	AC	878 ms 134,876 KB
testcase_43	AC	859 ms 143,800 KB
testcase_44	AC	859 ms 143,204 KB
testcase_45	AC	857 ms 135,092 KB
testcase_46	AC	862 ms 138,716 KB
testcase_47	AC	862 ms 131,536 KB
testcase_48	AC	860 ms 146,932 KB
testcase_49	AC	860 ms 139,228 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input = lambda: sys.stdin.readline().rstrip()
# sys.setrecursionlimit(10**7)
# sys.set_int_max_str_digits(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
def lm1(LIST): return list(map(lambda x:x-1, LIST))
def mps(A):return [tuple(map(int, input().split())) for _ in range(A)]
def stoi(LIST):return list(map(int,LIST))
def itos(LIST):return list(map(str,LIST))
def atoi(LIST): return [ord(i)-ord("a") for i in LIST]
def Atoi(LIST): return [ord(i)-ord("A") for i in LIST]
def LT(LIST,N): return LIST[bisect.bisect_left(LIST,N)-1]
def LE(LIST,N): return LIST[bisect.bisect_right(LIST,N)-1]
def GT(LIST,N): return LIST[bisect.bisect_right(LIST,N)]
def GE(LIST,N): return LIST[bisect.bisect_left(LIST,N)]
def bitA(X,A):return X & 1<<A == 1<<A
def gtoi(x,y,h,w):return x*w+y
import math
import bisect
import heapq
import time
import random as rd
import itertools
from copy import copy as cc
from copy import deepcopy as dc
from itertools import accumulate, product
from collections import Counter, defaultdict, deque
def ceil(U,V):return (U+V-1)//V
def modf1(N,MOD):return (N-1)%MOD+1
def printmat(list):
    for i in list:print(*i)
m4 = [[1,0],[0,1],[-1,0],[0,-1]]
m8 = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
inf = (1<<63)-1
mod = 998244353

start_time = time.time()
n = int(input())
omote = []
ura = []
max_limit = 50
for i in range(n):
    a,b = mp()
    omote.append(a)
    ura.append(b)
width = 3
depth = 3

def output(sosa_arr):
    print(len(sosa_arr))
    for i,j in sosa_arr:print(i+1,j+1)

def calc_score(x,y):
    return max(abs(500000000000000000-x),abs(500000000000000000-y))

def calc_all_score(a,b,X):
    ErrorA = abs(500000000000000000 - a[0])
    ErrorB = abs(500000000000000000 - b[0])
    Score = (int)(2000000.0 - 100000.0 * math.log10(1.0 * max(ErrorA, ErrorB) + 1.0))
    if ErrorA == 0 and ErrorB == 0:
        Score = 2000050 - X
    return Score


def greedy(a,b):
    sosa = []
    for kaisu in range(max_limit):
        score = calc_score(a[0],b[0])
        choose_card = 0
        for i in range(1,n):
            na,nb = (a[0]+a[i])/2, (b[0]+b[i])/2
            now_score = calc_score(na,nb)
            if now_score < score:
                score = now_score
                choose_card = i
        a[0],b[0],a[choose_card],b[choose_card] = (a[0]+a[choose_card])/2, (b[0]+b[choose_card])/2,\
                                                  (a[0]+a[choose_card])/2, (b[0]+b[choose_card])/2
        if choose_card == 0:break
        sosa.append([0,choose_card])
    return a,b,sosa


def remove_huyou(A):
    while len(A) != 1:
        if A[-1] == A[-2]:A.pop()
        else:break
    return A


def hanei_0(Score,A,B,Sosa):
    choose_card = 0
    Score = calc_score(A[0],B[0])
    for i in range(1, n):
        na, nb = (A[0] + A[i]) / 2, (B[0] + B[i]) / 2
        now_score = calc_score(na, nb)
        if now_score < Score:
            Score = now_score
            choose_card = i
    A[0], B[0], A[choose_card], B[choose_card] = (A[0] + A[choose_card]) / 2, (B[0] + B[choose_card]) / 2, \
                                                 (A[0] + A[choose_card]) / 2, (B[0] + B[choose_card]) / 2
    if choose_card != 0:Sosa.append([0, choose_card])
    return [Score,A,B,Sosa]


def beam_search(a,b,sosa_Arr):
    koho = [[calc_score(a[0],b[0]), cc(a), cc(b), sosa_Arr]]  # 次stepで反映したときのscore,今のa,今のb,今の操作
    heapq.heapify(koho)
    best_score = calc_score(a[0],b[0])
    for dep in range(depth):
        now_koho = []
        while not (len(koho) == 0 or len(now_koho) == width):
            nxt = heapq.heappop(koho)
            if nxt[0] > best_score:break
            now_koho.append(nxt)
        koho.clear()
        best_score = now_koho[0][0]
        for Score,A,B,Sosa in now_koho:
            if len(Sosa) == max_limit:continue
            heapq.heappush(koho, dc([Score, A, B, Sosa]))
            for i in range(n):
                for j in range(i+1,n):
                    if Sosa and Sosa[-1] == [i,j]:continue
                    ac = cc(A)
                    bc = cc(B)
                    sosac = cc(Sosa)
                    na,nb = (a[i]+a[j])/2, (b[i]+b[j])/2
                    ac[i],ac[j],bc[i],bc[j] = na,na,nb,nb
                    hanei_a,hanei_b = (na+ac[0])/2, (nb+bc[0])/2
                    now_score = calc_score(hanei_a,hanei_b)
                    sosac.append([i,j])
                    if A == ac and B == bc:continue
                    heapq.heappush(koho,[now_score,ac,bc,sosac])
    best_koho = heapq.heappop(koho)
    best_koho[3] = remove_huyou(best_koho[3])
    best_koho = hanei_0(*best_koho)
    return best_koho


def main():
    sosa_arr = []
    global omote
    global ura
    while time.time()-start_time <= 0.8:
        pred_score,na,nb,sosa_arr = beam_search(omote,ura,sosa_arr)
        omote = na
        ura = nb
    output(sosa_arr)
    #print(calc_all_score(omote,ura,len(sosa_arr)))
    #na,nb,sosa_arr = greedy(omote,ura)

main()

yukicoder

結果

テストケース

ソースコード