#955594 (PyPy3) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	Keroru
提出日時	2024-02-25 16:14:52
言語	PyPy3 (7.3.15)
結果	AC
実行時間	383 ms / 1,000 ms
コード長	13,657 bytes
コンパイル時間	199 ms
コンパイル使用メモリ	81,828 KB
実行使用メモリ	91,208 KB
スコア	19,301,248
最終ジャッジ日時	2024-02-25 16:15:17
合計ジャッジ時間	20,324 ms
ジャッジサーバーID （参考情報）	judge12 / judge15
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	347 ms 87,456 KB
testcase_01	AC	356 ms 88,536 KB
testcase_02	AC	346 ms 87,264 KB
testcase_03	AC	345 ms 88,452 KB
testcase_04	AC	345 ms 88,056 KB
testcase_05	AC	362 ms 89,016 KB
testcase_06	AC	349 ms 88,264 KB
testcase_07	AC	337 ms 89,668 KB
testcase_08	AC	328 ms 87,468 KB
testcase_09	AC	355 ms 88,784 KB
testcase_10	AC	348 ms 87,384 KB
testcase_11	AC	361 ms 89,492 KB
testcase_12	AC	370 ms 91,208 KB
testcase_13	AC	355 ms 89,160 KB
testcase_14	AC	349 ms 89,152 KB
testcase_15	AC	347 ms 87,700 KB
testcase_16	AC	357 ms 88,304 KB
testcase_17	AC	341 ms 87,448 KB
testcase_18	AC	364 ms 89,488 KB
testcase_19	AC	333 ms 87,160 KB
testcase_20	AC	366 ms 90,044 KB
testcase_21	AC	366 ms 89,284 KB
testcase_22	AC	356 ms 88,888 KB
testcase_23	AC	322 ms 86,516 KB
testcase_24	AC	319 ms 86,740 KB
testcase_25	AC	331 ms 87,872 KB
testcase_26	AC	357 ms 88,076 KB
testcase_27	AC	346 ms 87,916 KB
testcase_28	AC	337 ms 87,748 KB
testcase_29	AC	334 ms 86,992 KB
testcase_30	AC	383 ms 89,264 KB
testcase_31	AC	354 ms 87,480 KB
testcase_32	AC	342 ms 89,084 KB
testcase_33	AC	350 ms 87,456 KB
testcase_34	AC	349 ms 87,704 KB
testcase_35	AC	337 ms 86,800 KB
testcase_36	AC	320 ms 87,648 KB
testcase_37	AC	351 ms 89,008 KB
testcase_38	AC	351 ms 88,420 KB
testcase_39	AC	372 ms 89,096 KB
testcase_40	AC	363 ms 89,424 KB
testcase_41	AC	354 ms 89,028 KB
testcase_42	AC	363 ms 88,732 KB
testcase_43	AC	341 ms 87,744 KB
testcase_44	AC	370 ms 89,244 KB
testcase_45	AC	368 ms 87,724 KB
testcase_46	AC	370 ms 89,088 KB
testcase_47	AC	355 ms 88,748 KB
testcase_48	AC	357 ms 89,700 KB
testcase_49	AC	325 ms 88,172 KB

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

ソースコード

raw source code

# quick score =  4458447 average 445844.7
# All processes finished in 0 hour 0 min 7 sec

# ポテンシャル（カード１と交換したときの最大スコア）でスコアリング
# quick score =  5228760 average 522876.0
# All processes finished in 0 hour 0 min 10 sec

import time
START=ALL_START=st=time.time()

import os
#import numpy as np
import sys
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline#;input=lambda:sys.stdin.readline().rstrip()

file_path='keroru'
if os.path.isdir(file_path):
    prod_env=False
    from PIL import Image,ImageDraw,ImageFont
    TLE1=10
    TLE2=12
else:
    prod_env=True
    TLE1=1.3
    TLE2=1.6
    
print_buffer=[]
quick_score=0

TEMP_START = 1000
TEMP_END = 100

movie_frame_size=100
images=[]

hash_id=hash(st)
show_flg=False
if not prod_env:
    import os
    show_flg=True

def log(*inp, end='\n'): # output time elapsed since the last time this function was called or the program started
    if prod_env:
        return
    global st
    now=time.time()
    if show_flg:
        tmp_print(str(int((now-st)*1000)/1000)+' sec elapsed:',*inp,end=end,flush=True)
    rt,st=now-st,now
    return rt

##############  I/O  ###############################################################
file_no=0
input_file=''
output_file=''
if prod_env:
    if str(print)!="<built-in function print>":
        del print
        tmp_print=print
        def print(*x,flush=True):
            tmp_print(*x,flush=True)
    
def IO_refresh(f_num=None):
    # in の f_num.txtから入力を全て読んでqueueに入れる。ローカルではinput()を上書きしてqueueからFIFOで返す関数にする。
    if prod_env:
        return
    global file_no,output_file,input_file,input_que,print
    if f_num==None:
        file_no+=1
    else:
        file_no=f_num
    input_file="in/"+str(10000+file_no)[1:]+".txt"
    output_file="out/abcd_"+str(10000+file_no)[1:]+".txt"
    
    input_que=deque()
    with open(input_file) as fin:
        for ln in fin.readlines():
            input_que+=ln.rstrip(),
    
    with open(output_file, mode='w') as f:
        f.write('')

if not prod_env:
    def input():
        return input_que.popleft()

    # Outputの度にファイルセーブしてると遅いので、1テストケース完了まではプリントバッファに貯めておいて最後にtxtファイルにOutputする
    if str(print)!="<built-in function print>":
        del print
    tmp_print=print
    def print(*x,flush=True,file=None):
        global print_buffer
        if file==sys.stderr:
            return
        print_buffer+=str(' '.join(map(str,x)))+'\n',
        # show(x) #デバッグ用
    
    def _print(*x,flush=True,file=None): # 直書き
        with open(output_file, mode='a') as f:
            f.write(str(' '.join(map(str,x)))+'\n')
    
    def print_all():
        global print_buffer
        with open(output_file, mode='a') as f:
            for x in print_buffer:
                f.write(x)
        print_buffer=[]

    def debug_print(*x,outputfile=None,mode='a'):
        global file_no
        if outputfile==None:
            outputfile="outs/debug"+str(10000+file_no)[1:]+".txt"
        with open(outputfile, mode=mode) as f:
            f.write(str(' '.join(map(str,x)))+'\n',)
        print_buffer=[]
else:
    def print_all():
        return
    def debug_print(*x,outputfile=None,mode='a'):
        return

##############  I/O  ###############################################################

##############  Template  ###############################################################
import math,time,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict

def I():return int(input())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def StoLI():return [ord(i)-97 for i in input()]
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        if prod_env:
            0
            #print('#',*inp,end=end)
        else:
            tmp_print('#',*inp,end=end)

mo=10**9+7
mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)]
compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
##############  Template  ###############################################################

##############  Visulaizers  ###############################################################
def convert_hsv_to_rgb(h,s,v):
    r=g=b=v*255
    if s>0.0:
        h*=6.0
        i=int(h)
        f=h-i
        if i==0:g*=1-s*(1-f);b*=1-s
        elif i==1:r*=1-s*f;b*=1-s
        elif i==2:r*=1-s;b*=1-s*(1-f)
        elif i==3:r*=1-s;g*=1-s*f
        elif i==4:r*=1-s*(1-f);g*=1-s
        elif i==5:g*=1-s;b*=1-s*f
    r,g,b=map(int,(r,g,b))
    return r,g,b

def visualize(a,ans,score=0,pseudo_ans=[],show_im=False,comment=None,case_num=0,col_type=''):
    #global n,m,e,pols,size_of_pols,pos_pols,v,errs
    n=len(a)//2
    if prod_env:
        return
    h=w=n
    ox=oy=100
    x_unit=y_unit=30
    W=ox*2+x_unit*w
    H=oy*2+y_unit*h
    
    im = Image.new("RGB", (H,W), (256,256,256))
    draw = ImageDraw.Draw(im)
    
    font = ImageFont.truetype("arial.ttf", 40)
    string_to_show=('ID '+str(case_num)+" : Score = "+str(score))
    draw.text((20, 5), string_to_show, 'blue', font=font)
    #draw.multiline_text((0+q*2, W+1+q), str(score), fill=(0, 0, 0), font=ImageFont.truetype("arial.ttf", 15))
    if comment!=None:
        string_to_show=str(comment)
        draw.text((20, 5+oy+y_unit*h), string_to_show, 'blue', font=font)
    
    def drawPoint(x,y,col,cut=0):
        x,y=y,x
        r,g,b=col
        draw.rectangle((x*x_unit+ox+cut,y*y_unit+oy+cut,(x+1)*x_unit+ox-cut,(y+1)*y_unit+oy-cut),(r,g,b,0))
    
    def drawCell(x,y,col=(250,80,80)):
        x,y=y,x
        r,g,b=col
        size=0
        width=1
        x1,y1,x2,y2=(x-size)*x_unit+ox,(y-size)*y_unit+oy,(x+1+size)*x_unit+ox,(y+1+size)*y_unit+oy
        draw.rectangle((x1,y1,x2,y2),outline=(200,200,200,0),width=width,fill=col)

    def drawBar(x,y,h,col=(250,80,80),size=0):
        x,y=y,x
        r,g,b=col
        #size=0
        width=1
        x1,y1,x2,y2=(x-size)*x_unit+ox,(y-h-size)*y_unit+oy,(x+1+size)*x_unit+ox,(y+1+size)*y_unit+oy
        draw.rectangle((x1,y1,x2,y2),outline=(200,200,200,0),width=width,fill=col)

    def drawLine(x,y,u,v,col=(20,20,20),dd=0):
        x,y=y,x
        u,v=v,u
        r,g,b=col
        size=0
        width=2
        x1,y1,x2,y2=x*x_unit+ox,y*y_unit+oy,u*x_unit+ox,v*y_unit+oy
        draw.line((x1+dd,y1+dd,x2+dd,y2+dd),width=width,fill=col)
    
    def drawEdge(x,y,u,v,col=(20,20,20),dd=0):
        x,y=y,x
        u,v=v,u
        r,g,b=col
        size=0
        width=2
        x1,y1,x2,y2=x*x_unit+ox,y*y_unit+oy,u*x_unit+ox,v*y_unit+oy
        draw.line((x1+dd,y1+dd,x2+dd,y2+dd),width=width,fill=col)
    
    # 15:15
    mx=max(a)
    max_h=20
    n=len(a)//2
    drawLine(max_h*5/10,-1,max_h*5/10,n+1,col=(20,20,20))
    for j in range(n):
        H,S,V=(a[j])/mx,0.7,0.7
        col=convert_hsv_to_rgb(H,S,V)
        h=int(max_h*a[j]/10**17/10)
        drawBar(max_h,j,h,col)

    x_shift=20
    drawLine(max_h*5/10+x_shift,-1,max_h*5/10+x_shift,n+1,col=(20,20,20))
    for j in range(n):
        H,S,V=(a[j+n])/mx,0.7,0.7
        col=convert_hsv_to_rgb(H,S,V)
        h=int(max_h*a[j+n]/10**17/10)
        drawBar(max_h+x_shift,j,h,col,size=0)

    if show_im:
        im.show()
    
    #im=visualize(i,show_im=True)
    #images=[im]
    return im
##############  Visulaizers  ###############################################################

##############  read_input  ###############################################################
def read_input(test_case):
    IO_refresh(test_case)
    min_x=10**17
    max_x=10**18-1
    a=[]
    b=[]
    if prod_env:
        n=I()
        for i in range(n):
            x,y=LI()
            a+=x,
            b+=y,
    else:
        n=45
        a=RLI(n,min_x,max_x)
        b=RLI(n,min_x,max_x)
    return n,a,b

##############  read_input  ###############################################################

def switch(i,j,a):
    n=len(a)//2
    x,y=a[i],a[j]
    s,t=a[i+n],a[j+n]
    a[i],a[j]=(x+y)//2,(x+y)//2
    a[i+n],a[j+n]=(s+t)//2,(s+t)//2
    return a
    

##############  solve  ############################################################### 
#def solve(n,a,b,b_width=40,loop_time=50):
def solve(n,a,b,b_width=28,loop_time=28):
    T=50
    mid=5*10**17
    A=a[:]+b[:]
    
    def calc_score(x,y):
        return -int(2_000_000-100_000*math.log(max(abs(x-mid),abs(y-mid))+1,10))
    
    def calc_pot_score(a):
        rt=min(math.log(max(abs(2*mid-a[0]-a[i]),abs(2*mid-a[n]-a[i+n]))+1,10)for i in range(1,n))
        return rt
    
    def make_final_change(score,ans,a):
        mn=inf
        for i in range(1,n):
            if mn>math.log(max(abs(2*mid-a[0]-a[i]),abs(2*mid-a[n]-a[i+n]))+1,10):
                mn=math.log(max(abs(2*mid-a[0]-a[i]),abs(2*mid-a[n]-a[i+n]))+1,10)
                tmp=i
        ans+=0*n+tmp,
        a[0],a[n]=a[tmp],a[tmp+n]
        return score,ans,a
    
    q=[(calc_score(a[0],b[0]),[],a+b)]
    heapify(q)
    ans=[]
    for _ in range(T-1):
        nx=[]
        nx_id=[]
        c=0
        for score,ans,ca in q:
            final_score=score
            #show(-score,(i,j),ca[0],cb[0])
            #show([int(math.log(i,10)*100)/100 for i in ca],[int(math.log(i,10)*100)/100 for i in cb])
            if final_score==0:
                break
            
            for _ in range(loop_time):
                u=RI(0,n-1)
                v=RI(0,n-1)
                if u==v:
                    continue
                a=ca[:]
                a=switch(u,v,a)
                score=calc_pot_score(a)
                nx+=(score,ans+[u*n+v],a),
                nx_id+=(score,c),
                c+=1
                
        #heapify(nx)
        q=[]
        
        nx_id.sort(key=lambda x:x[0])
        #show(len(nx),len(nx_id),nx_id[:20])
        for _,i in nx_id[:b_width]:
            score,ans,a=nx[i]
            q+=(score,ans,a),
        #q+=mandatory,
        #show([(a[0],a[n]) for i,_,a in q],[-i for i,*_ in q])
    score,ans,a=heappop(nx)
    score,ans,a=make_final_change(score,ans,a)
    
    final_ans=[]
    #print(len(ans))
    for x in ans:
        i,j=divmod(x,n)
        A=switch(i,j,A)
        final_ans+=i*n+j,
    #show(A[0],A[n])
    ##############  solver  ###############################################################
    final_score=-calc_score(A[0],A[n])
    
    return final_ans,final_score


start_case=0
if prod_env:
    iteration=1
else:
    start_case=0
    iteration=1

total=0
total_rel=0
quick_score=0
scores=[]
for tc in range(iteration):
    START=time.time()
    random.seed(tc+start_case)
    
    ans=[]
    show_im_flag=False
    visualize_flag=False
    make_movie_flag=False
    show_im_flag&=visualize_flag
    
    n,a,b=read_input(tc+start_case)
    
    ######## solver choice ####################
    
    ans,score,*_=solve(n,a,b)
    
    print(len(ans))
    for x in ans:
        i,j=divmod(x,n)
        print(i+1,j+1)
    
    
    scores+=score,
    

    ######## solver choice ####################
    
    
    ######## output info to local ####################

    if not prod_env:
        elapsed_t=time.time()-START
        print_all()
                
        if visualize_flag or make_movie_flag:
            new_dir_path = 'img/'+str(hash_id)
            if not os.path.isdir(new_dir_path):
                os.mkdir(new_dir_path)
        
        if visualize_flag:
            a=a[:]+b[:]
            comment="laps = "+str(0)+" :hashID = "+str(hash_id)
            for x in ans:
                i,j=divmod(x,n)
                images+=visualize(a,ans,score=score,pseudo_ans=[],show_im=False,comment="Estimate",case_num=tc+start_case),
                a=switch(i,j,a)
                show(a[0],a[n])
            images+=visualize(a,ans,score=score,pseudo_ans=[],show_im=False,comment="last",case_num=tc+start_case),

            movie_1_frame_time=200
            comment="laps = "+str(0)+" :hashID = "+str(hash_id)
            #images[0].save('img/'+str(hash_id)+'/image_'+str(tc+start_case+10000)[1:]+'_a.png')
            images[0].save('img/'+str(hash_id)+'/mov_'+str(tc+start_case+10000)[1:]+'.gif', save_all=True
                       , append_images=images[1:]+[images[-1]]*10, optimize=False, duration=movie_1_frame_time, loop=2)

        elapsed_time=time.time()-START
        log_val=list(map(lambda x:round(math.log(max(x,1),10),3),[score]))
        info=['ID',str(tc+start_case+10000)[1:],score,elapsed_t]
        log_file='_logs.txt'
        with open(log_file, mode='a') as f:
            f.write(str(' '.join(map(str,info)))+'\n')
    
    quick_score+=score
    
    print(score,file=sys.stderr)
    if not prod_env:
        log(info)
        print_all()

    ######## output info to local ####################
    
if not prod_env:
    #show('(N,M,eps),cost/sum_v,cost/nn,rem_q_cnt,nn,log_val,score')
    now=time.time()
    hours=0
    mins=0
    secs=int(now-ALL_START)
    if secs>60:
        mins=secs//60
        secs%=60
        if mins>60:
            hours=mins//60
            mins%=60
    show('quick score = ',quick_score,'average',quick_score/iteration)
    show(f'All processes finished in {hours} hour {mins} min {secs} sec')

yukicoder

結果

テストケース

ソースコード