結果
問題 | No.5020 Averaging |
ユーザー | Koi |
提出日時 | 2024-02-25 15:55:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 991 ms / 1,000 ms |
コード長 | 2,181 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 80,896 KB |
スコア | 34,751,030 |
最終ジャッジ日時 | 2024-02-25 15:56:40 |
合計ジャッジ時間 | 52,553 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 986 ms
79,604 KB |
testcase_01 | AC | 988 ms
79,836 KB |
testcase_02 | AC | 986 ms
79,684 KB |
testcase_03 | AC | 988 ms
79,284 KB |
testcase_04 | AC | 987 ms
79,964 KB |
testcase_05 | AC | 987 ms
79,720 KB |
testcase_06 | AC | 988 ms
79,604 KB |
testcase_07 | AC | 986 ms
80,760 KB |
testcase_08 | AC | 987 ms
80,480 KB |
testcase_09 | AC | 987 ms
80,644 KB |
testcase_10 | AC | 988 ms
79,592 KB |
testcase_11 | AC | 986 ms
79,952 KB |
testcase_12 | AC | 986 ms
79,432 KB |
testcase_13 | AC | 986 ms
79,908 KB |
testcase_14 | AC | 987 ms
80,512 KB |
testcase_15 | AC | 987 ms
79,636 KB |
testcase_16 | AC | 986 ms
79,316 KB |
testcase_17 | AC | 987 ms
79,464 KB |
testcase_18 | AC | 987 ms
79,464 KB |
testcase_19 | AC | 987 ms
80,088 KB |
testcase_20 | AC | 986 ms
80,344 KB |
testcase_21 | AC | 985 ms
80,108 KB |
testcase_22 | AC | 986 ms
80,476 KB |
testcase_23 | AC | 987 ms
80,104 KB |
testcase_24 | AC | 986 ms
80,644 KB |
testcase_25 | AC | 987 ms
79,588 KB |
testcase_26 | AC | 986 ms
79,840 KB |
testcase_27 | AC | 987 ms
80,112 KB |
testcase_28 | AC | 987 ms
80,108 KB |
testcase_29 | AC | 987 ms
79,964 KB |
testcase_30 | AC | 988 ms
80,132 KB |
testcase_31 | AC | 986 ms
79,744 KB |
testcase_32 | AC | 991 ms
80,328 KB |
testcase_33 | AC | 987 ms
79,988 KB |
testcase_34 | AC | 987 ms
80,588 KB |
testcase_35 | AC | 986 ms
79,712 KB |
testcase_36 | AC | 987 ms
79,724 KB |
testcase_37 | AC | 986 ms
80,372 KB |
testcase_38 | AC | 987 ms
79,836 KB |
testcase_39 | AC | 987 ms
79,740 KB |
testcase_40 | AC | 986 ms
79,984 KB |
testcase_41 | AC | 987 ms
79,712 KB |
testcase_42 | AC | 988 ms
80,504 KB |
testcase_43 | AC | 987 ms
79,728 KB |
testcase_44 | AC | 987 ms
79,952 KB |
testcase_45 | AC | 987 ms
80,896 KB |
testcase_46 | AC | 987 ms
79,452 KB |
testcase_47 | AC | 987 ms
79,976 KB |
testcase_48 | AC | 987 ms
79,464 KB |
testcase_49 | AC | 988 ms
79,756 KB |
ソースコード
#ver4 #一番答えが大きくなるものを選ぶ(貪欲) #(i,j)を辞書順に調べる #解を変える適当山登り import time t0=time.time() import random random.seed(14) N=int(input()) A=[] B=[] cons=5*10**17 for _ in range(N): a,b=map(int,input().split()) A.append(a) B.append(b) A_base=[a for a in A] B_base=[b for b in B] op_cnt=0 #costは低ければ低いほどよい def calculate_cost(a,b): return max(abs(a-cons),abs(b-cons)) def op(u,v): global A global B a,b=A[u],A[v] c,d=B[u],B[v] A[u],A[v]=(a+b)//2,(a+b)//2 B[u],B[v]=(c+d)//2,(c+d)//2 cost=calculate_cost(A[0],B[0]) ans=[] while op_cnt<50: u=-1 v=-1 best_cost=cost for i in range(N): for j in range(i+1,N): if(i==0): new_cost=calculate_cost((A[i]+A[j])//2,(B[i]+B[j])//2) if(new_cost<best_cost): u=i v=j best_cost=new_cost if(v!=-1): break if(v==-1): break else: op_cnt+=1 op(u,v) ans.append([u,v]) cost=calculate_cost(A[0],B[0]) while op_cnt<50: (u,v)=ans[-1] ans.append([u,v]) op_cnt+=1 def calculate_cost_by_ans(ans): X=len(ans) cal_A=[a for a in A_base] cal_B=[b for b in B_base] for i in range(X): (u,v)=ans[i] a,b=cal_A[u],cal_A[v] c,d=cal_B[u],cal_B[v] cal_A[u],cal_A[v]=(a+b)//2,(a+b)//2 cal_B[u],cal_B[v]=(c+d)//2,(c+d)//2 # print(cal_A[0],cal_B[0]) return calculate_cost(cal_A[0],cal_B[0]) # print(cost) # print(A[0],B[0]) # print(calculate_cost_by_ans(ans),"?") while time.time()-t0<0.95: i=random.randint(0,len(ans)-1) (u,v)=ans[i] new_u=random.randint(0,N-1) new_v=random.randint(0,N-2) if(new_v==new_u): new_v+=1 # print(u,v) # print(new_u,new_v,"new") ans[i]=[new_u,new_v] new_cost=calculate_cost_by_ans(ans) # print(cost,"cost") # print(new_cost,"new_cost") if(cost<new_cost): ans[i]=[u,v] else: # print(cost,new_cost) cost=new_cost # print(cost) print(len(ans)) for (u,v) in ans: print(u+1,v+1)