#955316 (PyPy3) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	Keroru
提出日時	2024-02-25 14:17:01
言語	PyPy3 (7.3.15)
結果	AC
実行時間	380 ms / 1,000 ms
コード長	11,988 bytes
コンパイル時間	144 ms
コンパイル使用メモリ	81,828 KB
実行使用メモリ	84,860 KB
スコア	25,224,263
最終ジャッジ日時	2024-02-25 14:17:22
合計ジャッジ時間	19,314 ms
ジャッジサーバーID （参考情報）	judge13 / judge12
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	336 ms 83,712 KB
testcase_01	AC	380 ms 83,488 KB
testcase_02	AC	338 ms 83,292 KB
testcase_03	AC	350 ms 83,728 KB
testcase_04	AC	328 ms 84,064 KB
testcase_05	AC	346 ms 83,600 KB
testcase_06	AC	335 ms 83,748 KB
testcase_07	AC	332 ms 83,900 KB
testcase_08	AC	324 ms 83,236 KB
testcase_09	AC	340 ms 83,164 KB
testcase_10	AC	338 ms 83,540 KB
testcase_11	AC	341 ms 84,244 KB
testcase_12	AC	344 ms 83,300 KB
testcase_13	AC	348 ms 83,328 KB
testcase_14	AC	334 ms 83,388 KB
testcase_15	AC	330 ms 83,540 KB
testcase_16	AC	324 ms 83,384 KB
testcase_17	AC	333 ms 83,440 KB
testcase_18	AC	340 ms 83,820 KB
testcase_19	AC	335 ms 83,704 KB
testcase_20	AC	342 ms 83,512 KB
testcase_21	AC	343 ms 83,932 KB
testcase_22	AC	369 ms 83,668 KB
testcase_23	AC	315 ms 82,824 KB
testcase_24	AC	353 ms 83,724 KB
testcase_25	AC	325 ms 83,448 KB
testcase_26	AC	380 ms 84,428 KB
testcase_27	AC	339 ms 83,140 KB
testcase_28	AC	364 ms 83,520 KB
testcase_29	AC	321 ms 82,704 KB
testcase_30	AC	346 ms 83,656 KB
testcase_31	AC	332 ms 83,224 KB
testcase_32	AC	339 ms 82,976 KB
testcase_33	AC	347 ms 83,500 KB
testcase_34	AC	343 ms 83,920 KB
testcase_35	AC	329 ms 83,388 KB
testcase_36	AC	329 ms 83,452 KB
testcase_37	AC	332 ms 83,640 KB
testcase_38	AC	356 ms 84,860 KB
testcase_39	AC	338 ms 83,016 KB
testcase_40	AC	322 ms 82,976 KB
testcase_41	AC	325 ms 83,460 KB
testcase_42	AC	340 ms 83,660 KB
testcase_43	AC	341 ms 83,256 KB
testcase_44	AC	331 ms 83,616 KB
testcase_45	AC	338 ms 83,876 KB
testcase_46	AC	353 ms 84,324 KB
testcase_47	AC	340 ms 83,976 KB
testcase_48	AC	340 ms 83,636 KB
testcase_49	AC	317 ms 82,704 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_area(area,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
    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 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)
    
    mx=max(area)+1
    if col_type=='estimate':
        mx=max(area)+0.001
        mn=min(area)-0.001
    for i in range(h):
        for j in range(w):
            H,S,V=(area[i*w+j]+0.5)/mx,0.7,0.3
            col=convert_hsv_to_rgb(H,S,V)
            drawCell(i,j,col)
    
    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  ###############################################################


##############  solve  ############################################################### 
#def solve(n,a,b,b_width=40,loop_time=50): 
def solve(n,a,b,b_width=20,loop_time=20): 
    T=50
    mid=5*10**17
    A=a[:]+b[:]
    def switch(i,j,a):
        x,y=a[i],a[j]
        s,t=a[i+n],a[j+n]
        a[i],a[j]=[(x+y)//2]*2
        a[i+n],a[j+n]=[(s+t)//2]*2
        return a
    
    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=[]
        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_score(a[0],a[n])
                score=calc_pot_score(a)
                nx+=(score,ans+[u*n+v],a),
        heapify(nx)    
        q=[]
        for _ in range(b_width):
            score,ans,a=heappop(nx)
            q+=(score,ans,a),
            if not nx:
                break
        #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)
    
    print(len(ans))
    for x in ans:
        i,j=divmod(x,n)
        A=switch(i,j,A)
        print(i+1,j+1)
    #show(A[0],A[n])
    ##############  solver  ###############################################################
    final_score=-calc_score(A[0],A[n])
    return ans,final_score

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

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)
    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:
            comment="laps = "+str(0)+" :hashID = "+str(hash_id)
            im_ans=visualize_area(list(jd.mg.mu),score=score,pseudo_ans=[],show_im=False,comment="Estimate",case_num=tc+start_case,col_type='estimate')
            im_ans.save('img/'+str(hash_id)+'/image_'+str(tc+start_case+10000)[1:]+'_a.png')
        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

結果

テストケース

ソースコード