結果
問題 | No.1251 絶対に間違ってはいけない最小化問題 |
ユーザー |
👑 ![]() |
提出日時 | 2021-09-20 20:09:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 481 ms / 2,000 ms |
コード長 | 3,834 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 155,380 KB |
最終ジャッジ日時 | 2024-07-02 18:48:25 |
合計ジャッジ時間 | 23,513 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
class Binary_Indexed_Tree():def __init__(self, L, calc, unit, inv, index=1):""" calc を演算とする N 項の Binary Indexed Tree を作成calc: 演算 (2変数関数, 可換群)unit: 群 calc の単位元 (x+e=e+x=xを満たすe)inv : 群 calc の逆元 (1変数関数, x+y(x)=y(x)+x=e をみたす y(x))"""self.calc=calcself.unit=unitself.inv=invself.index=indexN=len(L)d=max(1,(N-1).bit_length())k=2**dX=[None]+[unit]*kself.num=kself.depth=dif L:for i in range(len(L)):p=i+1while p<=k:X[p]=self.calc(X[p],L[i])p+=p&(-p)self.data=Xdef index_number(self, k, index=1):""" 第 k 要素の値を出力する.k : 数列の要素index: 先頭の要素の番号"""return self.sum(k,k,index)def add(self, k, x, index=1):""" 第 k 要素に x を加え, 更新を行う.k : 数列の要素x : 加える値index: 先頭の要素の番号right:「左から」が「右から」になる"""p=k+(1-index)while p<=self.num:self.data[p]=self.calc(self.data[p],x)p+=p&(-p)def update(self, k, x, index=1):""" 第 k 要素を x に変え, 更新を行う.k: 数列の要素x: 更新後の値"""a=self.index_number(k,index)y=self.calc(self.inv(a),x)self.add(k,y,index)def sum(self, From, To, index=1):""" 第 From 要素から第 To 要素までの総和を求める.※From!=1を使うならば, 群でなくてはならない.From : 始まりTo : 終わりindex: 先頭の要素の番号"""alpha=max(1,From+(1-index))beta=min(self.num,To+(1-index))if alpha==1:return self.__section(beta)else:return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))def __section(self,x):""" B[1]+...+B[x] を求める. """S=self.unitwhile x>0:S=self.calc(self.data[x],S)x-=x&(-x)return Sdef all_sum(self):return self.data[-1]def binary_search(self, cond, index=1):""" cond(B[1]+...+B[k]) を満たす最小の k を返す.cond: 単調増加※ cond(uint)=True の場合の返り値は index-1※ cond(B[1]+...+B[k]) なる k が存在しない場合の返り値は self.num+index"""if cond(self.unit):return index-1j=0r=self.numt=rdata=self.dataalpha=self.unitfor _ in range(self.depth+1):if j+t<=self.num:beta=self.calc(alpha,data[j+t])if not cond(beta):alpha=betaj+=tt>>=1return j+indexdef __getitem__(self,index):if isinstance(index,int):return self.index_number(index,self.index)else:return [self.index_number(t,self.index) for t in index]def __setitem__(self,index,val):self.update(index,val,self.index)#==================================================from operator import add,negN=int(input())A=list(map(int,input().split()))B=list(map(int,input().split()))A_sort=sorted(A)A_ind={a:i for i,a in enumerate(A_sort)}T=Binary_Indexed_Tree([0]*N,add,0,neg,0)for a,b in zip(A,B):T.add(A_ind[a],b,0)B_sum=sum(B)X=A_sort[T.binary_search(lambda x:x>=(B_sum+1)//2,0)]Y=0for a,b in zip(A,B):Y+=b*abs(X-a)print(X,Y)