結果
問題 | No.1265 Balloon Survival |
ユーザー |
|
提出日時 | 2021-12-20 10:17:18 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 935 bytes |
コンパイル時間 | 13,101 ms |
コンパイル使用メモリ | 232,792 KB |
実行使用メモリ | 13,696 KB |
最終ジャッジ日時 | 2024-09-15 15:15:29 |
合計ジャッジ時間 | 16,363 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
package mainimport ("fmt""bufio""os""sort")func main() {r := bufio.NewReader(os.Stdin)w := bufio.NewWriter(os.Stdout)defer w.Flush()var n intfmt.Fscan(r, &n)xy := make([][2]int, n)for i := 0; i < n; i++ {var x, y intfmt.Fscan(r, &x, &y)xy[i] = [2]int{x, y}}dist := make([][3]int, n * (n-1) / 2)k := 0for i := 0; i < n; i++ {xi, yi := xy[i][0], xy[i][1]for j := i+1; j < n; j++ {xj, yj := xy[j][0], xy[j][1]d := (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj)dist[k] = [3]int{d, i, j}k++}}sort.Slice(dist, func(i, j int) bool {return dist[i][0] < dist[j][0]})dead := make([]bool, n)alive_n := nremove := 0for _, x := range dist {i, j := x[1], x[2]if i == 0 && !dead[j] {remove++dead[j] = truealive_n--} else if !dead[i] && !dead[j] {dead[i] = truedead[j] = true}if alive_n == 1 {break}}fmt.Fprintln(w, remove)}