結果
| 問題 | No.5020 Averaging |
| ユーザー |
 Keroru
|
| 提出日時 | 2024-02-25 13:49:41 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,911 bytes |
| コンパイル時間 | 149 ms |
| コンパイル使用メモリ | 81,828 KB |
| 実行使用メモリ | 277,516 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2024-02-25 13:50:10 |
| 合計ジャッジ時間 | 27,609 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
ソースコード
# quick score = 1079068 average 21581.36
# All processes finished in 0 hour 0 min 3 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):
T=50
mid=5*10**17
A=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]*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))
b_width=8
q=[(calc_score(a[0],b[0]),-1,-1,a+b)]
heapify(q)
ans=[]
for _ in range(T+1):
nx=[]
for score,i,j,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 i!=-1:
ans+=(i,j),
if final_score==0:
break
for u in range(n):
for v in range(u+1,n):
a=ca[:]
a=switch(u,v,a)
score=calc_score(a[0],a[n])
nx+=(score,u,v,a),
heapify(nx)
q=[]
for _ in range(b_width):
score,u,v,a=heappop(nx)
q+=(score,u,v,a),
#show([-i for i,*_ in q])
print(len(ans))
for i,j in ans:
print(i+1,j+1)
############## solver ###############################################################
return ans,-final_score
start_case=0
if prod_env:
iteration=1
else:
start_case=0
iteration=1
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')