結果
問題 | No.1280 Beyond C |
ユーザー | Yosh |
提出日時 | 2020-11-06 23:01:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 384 ms / 2,000 ms |
コード長 | 2,555 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 87,088 KB |
実行使用メモリ | 130,020 KB |
最終ジャッジ日時 | 2023-09-29 19:27:51 |
合計ジャッジ時間 | 8,696 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 268 ms
93,596 KB |
testcase_01 | AC | 268 ms
93,744 KB |
testcase_02 | AC | 269 ms
93,792 KB |
testcase_03 | AC | 262 ms
93,920 KB |
testcase_04 | AC | 264 ms
93,764 KB |
testcase_05 | AC | 259 ms
93,748 KB |
testcase_06 | AC | 263 ms
93,744 KB |
testcase_07 | AC | 262 ms
93,516 KB |
testcase_08 | AC | 264 ms
93,852 KB |
testcase_09 | AC | 267 ms
93,596 KB |
testcase_10 | AC | 267 ms
93,716 KB |
testcase_11 | AC | 275 ms
94,408 KB |
testcase_12 | AC | 268 ms
93,600 KB |
testcase_13 | AC | 273 ms
94,584 KB |
testcase_14 | AC | 272 ms
94,588 KB |
testcase_15 | AC | 329 ms
109,412 KB |
testcase_16 | AC | 309 ms
105,520 KB |
testcase_17 | AC | 324 ms
110,668 KB |
testcase_18 | AC | 332 ms
129,636 KB |
testcase_19 | AC | 320 ms
127,848 KB |
testcase_20 | AC | 378 ms
129,880 KB |
testcase_21 | AC | 378 ms
130,020 KB |
testcase_22 | AC | 384 ms
129,844 KB |
ソースコード
from __future__ import print_function from functools import reduce from operator import mul from collections import Counter from collections import deque from itertools import accumulate from queue import Queue from queue import PriorityQueue as pq from heapq import heapreplace from heapq import heapify from heapq import heappushpop from heapq import heappop from heapq import heappush import heapq import time import random import bisect import itertools import collections from fractions import Fraction import fractions import string import math import operator import functools import copy import array import re import sys sys.setrecursionlimit(500000) input = sys.stdin.readline # def # eprint(*args, **kwargs): # print(*args, file=sys.stderr, **kwargs) # return # from fractions import gcd # from math import gcd # def lcm(n, m): # return int(n * m / gcd(n, m)) # def coprimize(p, q): # common = gcd(p, q) # return (p // common, q // common) # def find_gcd(list_l): # x = reduce(gcd, list_l) # return x def combinations_count(n, r): r = min(r, n - r) numer = reduce(mul, range(n, n - r, -1), 1) denom = reduce(mul, range(1, r + 1), 1) return numer // denom mod = 1000000007 def combinations_count_mod(n, r): r = min(r, n - r) numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1) denom = pow(reduce(lambda x, y: x * y % mod, range(1, r + 1), 1), mod - 2, mod) return numer * denom % mod # def solve(): n, m, c = map(int, input().strip().split()) a = sorted(list(map(int, input().strip().split()))) b = sorted(list(map(int, input().strip().split()))) + [sys.maxsize] # eprint('a,b ',end=':\n') # eprint(a,b) cnt = 0 for i in range(n): # if a[i] * b[0] > c: cnt += m continue # # def is_ok(m): if a[i] * b[m] > c: return True else: return False # にぶたんのメイン処理 ok = m ng = 0 while abs(ok - ng) > 1: # 条件を満たすindex ok と 条件を満たさないindex ng が ちょうど 1 ズレる(ちょうどokとngで境界になる)まで続ける mid = (ok + ng) // 2 if is_ok(mid): ok = mid else: ng = mid cnt += (m - 1) - ng # eprint('a[i],b[ok],cnt,m,ng,ok ',end=':\n') # eprint(a[i],b[ok],cnt,m,ng,ok) # if (m - 1) - ng < 0: # eprint('error: n-ng, ', end=':\n') # eprint(n - ng) # eprint('cnt ',end=':\n') # eprint(cnt) print(cnt / (n * m))