結果
| 問題 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 48 TLE * 2 |
ソースコード
# 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')