結果
問題 | No.5020 Averaging |
ユーザー |
|
提出日時 | 2024-02-25 13:57:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 360 ms / 1,000 ms |
コード長 | 11,038 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 87,612 KB |
スコア | 20,956,315 |
最終ジャッジ日時 | 2024-02-25 13:57:55 |
合計ジャッジ時間 | 18,033 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
# quick score = 1079068 average 21581.36# All processes finished in 0 hour 0 min 3 secimport timeSTART=ALL_START=st=time.time()import os#import numpy as npimport sysread=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=Falsefrom PIL import Image,ImageDraw,ImageFontTLE1=10TLE2=12else:prod_env=TrueTLE1=1.3TLE2=1.6print_buffer=[]quick_score=0TEMP_START = 1000TEMP_END = 100movie_frame_size=100images=[]hash_id=hash(st)show_flg=Falseif not prod_env:import osshow_flg=Truedef log(*inp, end='\n'): # output time elapsed since the last time this function was called or the program startedif prod_env:returnglobal stnow=time.time()if show_flg:tmp_print(str(int((now-st)*1000)/1000)+' sec elapsed:',*inp,end=end,flush=True)rt,st=now-st,nowreturn rt############## I/O ###############################################################file_no=0input_file=''output_file=''if prod_env:if str(print)!="<built-in function print>":del printtmp_print=printdef 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:returnglobal file_no,output_file,input_file,input_que,printif f_num==None:file_no+=1else:file_no=f_numinput_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 printtmp_print=printdef print(*x,flush=True,file=None):global print_bufferif file==sys.stderr:returnprint_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_bufferwith 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_noif 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():returndef debug_print(*x,outputfile=None,mode='a'):return############## I/O ############################################################################# Template ###############################################################import math,time,randomfrom heapq import heappush,heappop,heapifyfrom collections import deque,defaultdictdef 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 rtdef show(*inp,end='\n'):if show_flg:if prod_env:0#print('#',*inp,end=end)else:tmp_print('#',*inp,end=end)mo=10**9+7mo=998244353inf=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*255if s>0.0:h*=6.0i=int(h)f=h-iif i==0:g*=1-s*(1-f);b*=1-selif i==1:r*=1-s*f;b*=1-selif i==2:r*=1-s;b*=1-s*(1-f)elif i==3:r*=1-s;g*=1-s*felif i==4:r*=1-s*(1-f);g*=1-selif i==5:g*=1-s;b*=1-s*fr,g,b=map(int,(r,g,b))return r,g,bdef 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,errsif prod_env:returnh=w=nox=oy=100x_unit=y_unit=30W=ox*2+x_unit*wH=oy*2+y_unit*him = 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,xr,g,b=coldraw.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,xr,g,b=colsize=0width=1x1,y1,x2,y2=(x-size)*x_unit+ox,(y-size)*y_unit+oy,(x+1+size)*x_unit+ox,(y+1+size)*y_unit+oydraw.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,xu,v=v,ur,g,b=colsize=0width=2x1,y1,x2,y2=x*x_unit+ox,y*y_unit+oy,u*x_unit+ox,v*y_unit+oydraw.line((x1+dd,y1+dd,x2+dd,y2+dd),width=width,fill=col)mx=max(area)+1if col_type=='estimate':mx=max(area)+0.001mn=min(area)-0.001for i in range(h):for j in range(w):H,S,V=(area[i*w+j]+0.5)/mx,0.7,0.3col=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**17max_x=10**18-1a=[]b=[]if prod_env:n=I()for i in range(n):x,y=LI()a+=x,b+=y,else:n=45a=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=12,loop_time=50):T=50mid=5*10**17A=a[:]B=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]*2a[i+n],a[j+n]=[(s+t)//2]*2return adef calc_score(x,y):return -int(2_000_000-100_000*math.log(max(abs(x-mid),abs(y-mid))+1,10))q=[(calc_score(a[0],b[0]),[],a+b)]heapify(q)ans=[]for _ in range(T):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:breakfor _ in range(loop_time):u=RI(0,n-1)v=RI(0,n-1)if u==v:continuea=ca[:]a=switch(u,v,a)score=calc_score(a[0],a[n])nx+=(score,ans+[u*n+v],a),heapify(nx)q=[]for _ in range(b_width):score,ans,a=heappop(nx)q+=(score,ans,a),#show([(a[0],a[n]) for i,_,a in q],[-i for i,*_ in q])score,ans,a=heappop(nx)print(len(ans))for x in ans:i,j=divmod(x,n)print(i+1,j+1)############## solver ###############################################################return ans,-final_scorestart_case=0if prod_env:iteration=1else:start_case=0iteration=1total=0total_rel=0quick_score=0scores=[]for tc in range(iteration):START=time.time()random.seed(tc+start_case)ans=[]show_im_flag=Falsevisualize_flag=Falsemake_movie_flag=Falseshow_im_flag&=visualize_flagn,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()-STARTprint_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()-STARTlog_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+=scoreprint(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=0mins=0secs=int(now-ALL_START)if secs>60:mins=secs//60secs%=60if mins>60:hours=mins//60mins%=60show('quick score = ',quick_score,'average',quick_score/iteration)show(f'All processes finished in {hours} hour {mins} min {secs} sec')