# quick score = 4458447 average 445844.7 # All processes finished in 0 hour 0 min 7 sec # ポテンシャル(カード1と交換したときの最大スコア)でスコアリング # 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)!="": 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)!="": 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')