結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 16:24:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 943 ms / 1,000 ms |
コード長 | 2,469 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 81,080 KB |
スコア | 27,955,458 |
最終ジャッジ日時 | 2024-02-25 16:26:06 |
合計ジャッジ時間 | 50,308 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 939 ms
80,976 KB |
testcase_01 | AC | 941 ms
79,424 KB |
testcase_02 | AC | 940 ms
80,168 KB |
testcase_03 | AC | 940 ms
80,196 KB |
testcase_04 | AC | 941 ms
79,884 KB |
testcase_05 | AC | 943 ms
80,456 KB |
testcase_06 | AC | 940 ms
80,604 KB |
testcase_07 | AC | 939 ms
80,040 KB |
testcase_08 | AC | 939 ms
79,552 KB |
testcase_09 | AC | 939 ms
79,828 KB |
testcase_10 | AC | 941 ms
79,732 KB |
testcase_11 | AC | 941 ms
79,612 KB |
testcase_12 | AC | 940 ms
79,580 KB |
testcase_13 | AC | 940 ms
79,396 KB |
testcase_14 | AC | 940 ms
79,684 KB |
testcase_15 | AC | 940 ms
79,704 KB |
testcase_16 | AC | 940 ms
79,984 KB |
testcase_17 | AC | 939 ms
79,632 KB |
testcase_18 | AC | 940 ms
80,848 KB |
testcase_19 | AC | 939 ms
80,088 KB |
testcase_20 | AC | 940 ms
79,444 KB |
testcase_21 | AC | 939 ms
79,840 KB |
testcase_22 | AC | 941 ms
80,100 KB |
testcase_23 | AC | 940 ms
79,948 KB |
testcase_24 | AC | 940 ms
80,840 KB |
testcase_25 | AC | 940 ms
79,564 KB |
testcase_26 | AC | 940 ms
79,632 KB |
testcase_27 | AC | 939 ms
79,556 KB |
testcase_28 | AC | 939 ms
79,908 KB |
testcase_29 | AC | 940 ms
79,632 KB |
testcase_30 | AC | 940 ms
79,572 KB |
testcase_31 | AC | 940 ms
80,108 KB |
testcase_32 | AC | 940 ms
79,928 KB |
testcase_33 | AC | 939 ms
79,872 KB |
testcase_34 | AC | 939 ms
79,764 KB |
testcase_35 | AC | 940 ms
79,668 KB |
testcase_36 | AC | 939 ms
80,764 KB |
testcase_37 | AC | 940 ms
80,148 KB |
testcase_38 | AC | 940 ms
80,000 KB |
testcase_39 | AC | 940 ms
79,448 KB |
testcase_40 | AC | 939 ms
79,464 KB |
testcase_41 | AC | 939 ms
79,576 KB |
testcase_42 | AC | 938 ms
79,584 KB |
testcase_43 | AC | 938 ms
79,812 KB |
testcase_44 | AC | 939 ms
79,932 KB |
testcase_45 | AC | 939 ms
79,804 KB |
testcase_46 | AC | 939 ms
79,600 KB |
testcase_47 | AC | 939 ms
79,736 KB |
testcase_48 | AC | 939 ms
81,080 KB |
testcase_49 | AC | 939 ms
79,696 KB |
ソースコード
from time import time start = time() import sys from random import randint,sample from itertools import combinations from collections import defaultdict def input(): return sys.stdin.readline().rstrip() def ii(): return int(input()) def ms(): return map(int, input().split()) def li(): return list(map(int,input().split())) # //////////////////////////////// N = ii() A = list() B = list() for i in range(N): a,b = ms() A.append(a) B.append(b) NUM = [i for i in range(2,N)] STAND = 5*pow(10,17) def create_abs(A,B,V1,V2,PREV): ABS = list() for v in range(1,N): na,nb = (A[0]+A[v])//2,(B[0]+B[v])//2 if A[0]==A[v] and B[0]==B[v]: continue if PREV[(0,v)]==(na,nb): continue n1,n2 = abs(na-STAND),abs(nb-STAND) tmp = max(V1,V2)-max(n1,n2) ABS.append((tmp,v)) ABS.sort(reverse=True) return ABS def other_merge(A,B,PREV): # STANDにできるだけ近いやつを作る CAND = list() for (u,v) in combinations(NUM,2): if A[u]==A[v] and B[u]==B[v]: continue na,nb = (A[u]+A[v])//2,(B[u]+B[v])//2 if PREV[(u,v)]==(na,nb): continue n1,n2 = abs(na-STAND),abs(nb-STAND) CAND.append((max(n1,n2),u,v)) CAND.sort() ind = randint(0,5) u,v = CAND[ind][1],CAND[ind][2] return u,v def play(A,B): global MAXV,BEST_ANS TURN = 0 ANS = list() V1,V2 = abs(A[0]-STAND),abs(B[0]-STAND) flag = False PREV = defaultdict(tuple) while TURN<50: if time()-start>0.9: return if flag: u,v = sample(NUM,2) flag = False else: ABS = create_abs(A,B,V1,V2,PREV) if ABS[0][0]==0: # 頭打ちになったら1以外とマージする u,v = sample(NUM,2) elif A[0]==A[ABS[0][1]] and B[0]==B[ABS[0][1]]: u,v = sample(NUM,2) elif ABS[0][0]<=0: u,v = sample(NUM,2) else: u,v = 0,ABS[0][1] flag = True ANS.append((u+1,v+1)) na,nb = (A[u]+A[v])//2,(B[u]+B[v])//2 if PREV[(u,v)]==(na,nb): while PREV[(u,v)]==(na,nb): u,v = sample(NUM,2) na,nb = (A[u]+A[v])//2,(B[u]+B[v])//2 if u==0: n1,n2 = abs(na-STAND),abs(nb-STAND) V1,V2 = n1,n2 A[u],A[v],B[u],B[v] = na,na,nb,nb PREV[(u,v)] = (na,nb) PREV[(v,u)] = (na,nb) TURN += 1 if MAXV>max(V1,V2): MAXV = max(V1,V2) BEST_ANS = [a[:] for a in ANS] return BEST_ANS = list() MAXV = pow(10,18) while time()-start<0.9: AA = A[:] BB = B[:] play(AA,BB) print(len(BEST_ANS)) for u,v in BEST_ANS: print(u,v)