結果
問題 | No.1265 Balloon Survival |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-25 03:28:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 772 ms / 2,000 ms |
コード長 | 779 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 111,872 KB |
最終ジャッジ日時 | 2024-09-20 03:57:24 |
合計ジャッジ時間 | 10,955 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
from collections import dequefrom operator import itemgetterimport sysinput=sys.stdin.readlinedef main():N=int(input())P=[0]*Nfor i in range(N):P[i]=tuple(map(int,input().split()))dist=[0]*(N*(N-1)//2)I=[0]*(N*(N-1)//2)J=[0]*(N*(N-1)//2)k=0for i in range(N):for j in range(i+1,N):a,b=P[i][0]-P[j][0],P[i][1]-P[j][1]I[k]=i; J[k]=j; dist[k]=a*a+b*bk+=1A=sorted(range(N*(N-1)//2), key=lambda k:dist[k])Flag=[1]*NX=0for k in A:i=I[k]; j=J[k]if not(Flag[i] and Flag[j]):continueFlag[j]=0if i!=0:Flag[i]=0else:X+=1return Xif __name__=="__main__":print(main())