#955395 (PyPy3) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	Keroru
提出日時	2024-02-25 14:57:21
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	15,079 bytes
コンパイル時間	489 ms
コンパイル使用メモリ	81,828 KB
実行使用メモリ	77,944 KB
スコア	12,188,620
最終ジャッジ日時	2024-02-25 14:58:21
合計ジャッジ時間	50,720 ms
ジャッジサーバーID （参考情報）	judge13 / judge10

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	967 ms 77,816 KB
testcase_01	AC	919 ms 77,816 KB
testcase_02	AC	945 ms 77,816 KB
testcase_03	AC	928 ms 77,816 KB
testcase_04	AC	950 ms 77,816 KB
testcase_05	AC	906 ms 77,816 KB
testcase_06	AC	944 ms 77,816 KB
testcase_07	AC	914 ms 77,816 KB
testcase_08	AC	935 ms 77,816 KB
testcase_09	AC	912 ms 77,816 KB
testcase_10	AC	913 ms 77,816 KB
testcase_11	AC	922 ms 77,816 KB
testcase_12	AC	943 ms 77,816 KB
testcase_13	AC	940 ms 77,816 KB
testcase_14	AC	927 ms 77,816 KB
testcase_15	AC	956 ms 77,816 KB
testcase_16	AC	923 ms 77,816 KB
testcase_17	AC	958 ms 77,816 KB
testcase_18	AC	950 ms 77,816 KB
testcase_19	AC	967 ms 77,816 KB
testcase_20	AC	920 ms 77,816 KB
testcase_21	AC	957 ms 77,816 KB
testcase_22	AC	932 ms 77,816 KB
testcase_23	AC	946 ms 77,816 KB
testcase_24	AC	911 ms 77,816 KB
testcase_25	AC	933 ms 77,816 KB
testcase_26	AC	945 ms 77,816 KB
testcase_27	AC	952 ms 77,816 KB
testcase_28	AC	963 ms 77,816 KB
testcase_29	AC	990 ms 77,816 KB
testcase_30	AC	949 ms 77,816 KB
testcase_31	AC	944 ms 77,816 KB
testcase_32	AC	943 ms 77,816 KB
testcase_33	AC	951 ms 77,816 KB
testcase_34	AC	961 ms 77,944 KB
testcase_35	AC	985 ms 77,816 KB
testcase_36	AC	924 ms 77,816 KB
testcase_37	AC	962 ms 77,816 KB
testcase_38	AC	935 ms 77,816 KB
testcase_39	AC	991 ms 77,816 KB
testcase_40	AC	954 ms 77,816 KB
testcase_41	AC	977 ms 77,816 KB
testcase_42	AC	976 ms 77,816 KB
testcase_43	TLE	-
testcase_44	AC	984 ms 77,816 KB
testcase_45	AC	969 ms 77,816 KB
testcase_46	AC	957 ms 77,816 KB
testcase_47	TLE	-
testcase_48	AC	939 ms 77,816 KB
testcase_49	AC	970 ms 77,816 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)
    
    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

def solve2(n,a,b,b_width=20,loop_time=20,aneal_time=10**4): 
    T=50
    mid=5*10**17
    A=a[:]+b[:]
    a=A[:]
    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):
        return score,ans,a
    
    j=RI(1,n-1)
    idx=[0,j]
    t1,t2,t3=100,200,1000
    s,t=a[0]+a[j],a[n]+a[j+n]
    ave=max(abs(s-mid)/2,abs(t-mid)/2)
    aneal_time=0
    for i in range(aneal_time):
        show(idx)
        rng=RI(0,1000)
        if rng<=t1: # Add
            nx=RI(1,n-1)
            if nx in idx:
                continue
            nx_idx=idx+[nx]
            ns=s+a[nx]
            nt=t+a[nx+n]
        elif rng<=t2: # Remove
            if len(idx)==1:
                continue
            nx=RI(1,len(idx)-1)
            nx_idx=idx[:]
            nx_idx.pop(nx)
            ns=s-a[nx]
            nt=t-a[nx+n]
        elif rng<=t3: # Chg
            nx=RI(1,len(idx)-1)
            nx2=RI(1,n-1)
            if nx2 in idx:
                continue
            nx_idx=idx+[nx2]
            nx_idx.pop(nx)
            ns=s+a[nx2]-a[nx]
            nt=t+a[nx2+n]-a[nx+n]
        nx_ave=max(abs(ns/len(idx)-mid),abs(nt/len(idx)))
        if ave>nx_ave:
            ave=nx_ave
            idx=nx_idx
        
        if len(idx)>5:
            t1,t2,t3=0,200,1000
        elif len(idx)==2:
            t1,t2,t3=200,200,1000
        else:
            t1,t2,t3=100,200,1000
    
    tmp=inf
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                for l in range(k+1,n):
                    for m in range(l+1,n):
                        idx=(i,j,k,l,m)
                        s=sum([a[x] for x in idx])
                        t=sum([a[x+n] for x in idx])
                        if tmp>max(abs(s/len(idx)-mid),abs(t/len(idx))):
                            tmp=max(abs(s/len(idx)-mid),abs(t/len(idx)))
                            _idx=idx
    
    q=[(max(abs(mid-a[i]),abs(mid-a[i+n])),a[i],a[i+n],i,i+n)for i in _idx]
    ans=[]
    for _ in range(T):
        q.sort(key=lambda x:x[0])
        w,s,t,i,ii=q[0]
        e,x,y,j,jj=q[-1]
        a=switch(i,j,a)
        ans+=i*n+j,
        s,t,x,y=a[j],a[j+n],a[i],a[i+n] # a[i]==a[j] になってる
        w=max(abs(mid-a[j]),abs(mid-a[j+n]))
        e=max(abs(mid-a[i]),abs(mid-a[i+n]))
        q=q[1:-1]+[(w,s,t,i,ii),(e,x,y,j,jj)]
    
    ##############  solver  ###############################################################
    final_score=-calc_score(a[0],a[n])
    show((a[0],a[n]),s/len(idx),t/len(idx),[a[x] for x in idx])
    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,*_=solve2(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:
            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

結果

テストケース

ソースコード