結果
問題 |
No.2008 Super Worker
|
ユーザー |
![]() |
提出日時 | 2022-07-15 21:41:28 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,647 bytes |
コンパイル時間 | 81 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 57,168 KB |
最終ジャッジ日時 | 2024-06-27 17:17:30 |
合計ジャッジ時間 | 18,987 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 RE * 10 TLE * 1 -- * 12 |
ソースコード
import sys import numpy as np def cmp(a, b): a1, b1 = a a2, b2 = b return a1 + a2 * b1 >= a2 + a1 * b2 def argsort(A): n = A.shape[0] length = 20 INF = np.zeros(2, np.int64) INF[1] = 1 << 60 index = np.arange(n) work = np.empty(n, np.int64) for l in range(0, n, length): r = min(l + length, n) for i in range(l+1, r): if cmp(A[index[i-1]], A[index[i]]): continue tmp = index[i] a = A[tmp] j = i while j > l and not cmp(A[index[j-1]], a): index[j] = index[j-1] j -= 1 index[j] = tmp while length < n: work = index.copy() for l in range(0, n, 2 * length): li, ri = l, min(l + length, n) l_max, r_max = min(li + length, n), min(ri + length, n) tot = (l_max - li) + (r_max - ri) for i in range(l, l+tot): a = A[work[li]] if li < l_max else INF b = A[work[ri]] if ri < r_max else INF if cmp(a, b): index[i] = work[li] li += 1 else: index[i] = work[ri] ri += 1 length <<= 1 return index def main(): n = int(input()) AB = np.fromstring(sys.stdin.read(), np.int64, sep=' ').reshape(2, -1).T x = 1 ans = 0 mod = 1_000_000_007 idx = argsort(AB) AB = AB[idx] for i in range(n): a, b = AB[i] ans += a * x ans %= mod x *= b x %= mod print(ans) if __name__ == '__main__': main()