結果
問題 | No.1265 Balloon Survival |
ユーザー | tonnnura172 |
提出日時 | 2020-10-24 20:07:11 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,532 ms / 2,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 95 ms |
コンパイル使用メモリ | 10,876 KB |
実行使用メモリ | 71,332 KB |
最終ジャッジ日時 | 2023-09-28 20:43:59 |
合計ジャッジ時間 | 19,467 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
9,508 KB |
testcase_01 | AC | 30 ms
9,464 KB |
testcase_02 | AC | 31 ms
9,564 KB |
testcase_03 | AC | 31 ms
9,656 KB |
testcase_04 | AC | 31 ms
9,524 KB |
testcase_05 | AC | 30 ms
9,496 KB |
testcase_06 | AC | 31 ms
9,492 KB |
testcase_07 | AC | 32 ms
9,592 KB |
testcase_08 | AC | 31 ms
9,432 KB |
testcase_09 | AC | 31 ms
9,452 KB |
testcase_10 | AC | 30 ms
9,516 KB |
testcase_11 | AC | 30 ms
9,592 KB |
testcase_12 | AC | 30 ms
9,492 KB |
testcase_13 | AC | 31 ms
9,488 KB |
testcase_14 | AC | 153 ms
17,012 KB |
testcase_15 | AC | 120 ms
15,148 KB |
testcase_16 | AC | 60 ms
11,516 KB |
testcase_17 | AC | 736 ms
41,952 KB |
testcase_18 | AC | 75 ms
12,492 KB |
testcase_19 | AC | 64 ms
11,904 KB |
testcase_20 | AC | 155 ms
16,772 KB |
testcase_21 | AC | 349 ms
25,168 KB |
testcase_22 | AC | 208 ms
19,520 KB |
testcase_23 | AC | 233 ms
20,360 KB |
testcase_24 | AC | 1,532 ms
70,360 KB |
testcase_25 | AC | 1,527 ms
71,228 KB |
testcase_26 | AC | 1,496 ms
71,304 KB |
testcase_27 | AC | 1,515 ms
71,232 KB |
testcase_28 | AC | 1,478 ms
71,296 KB |
testcase_29 | AC | 1,499 ms
71,308 KB |
testcase_30 | AC | 1,531 ms
71,332 KB |
testcase_31 | AC | 1,531 ms
71,232 KB |
testcase_32 | AC | 1,516 ms
71,200 KB |
testcase_33 | AC | 1,521 ms
71,328 KB |
testcase_34 | AC | 31 ms
9,644 KB |
testcase_35 | AC | 30 ms
9,584 KB |
ソースコード
import sys, re from collections import deque, defaultdict, Counter from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement from operator import itemgetter, mul from copy import deepcopy from string import ascii_lowercase, ascii_uppercase, digits from bisect import bisect, bisect_left from heapq import heappush, heappop from functools import reduce def input(): return sys.stdin.readline().strip() def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(): return list(map(int, input().split())) def ZIP(n): return zip(*(MAP() for _ in range(n))) sys.setrecursionlimit(10 ** 9) INF = float('inf') mod = 10 ** 9 + 7 N = INT() xy = [LIST() for _ in range(N)] dist = [] for i, j in combinations(range(N), 2): x1, y1 = xy[i] x2, y2 = xy[j] d = (x1-x2)**2 + (y1-y2)**2 dist.append((d, i, j)) dist.sort() ans = 0 s = set() for _, i, j in dist: if i in s or j in s: # 既に爆発済み continue elif i == 0: # 取り除く ans += 1 s.add(j) else: # 爆発 s.add(i) s.add(j) print(ans)