Submission #67364858

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, 1000000), 100000000)
	sc.Scan()
	T, _ := strconv.Atoi(sc.Text())

	for i := 0; i < T; i++ {
		sc.Scan()
		N, _ := strconv.Atoi(sc.Text())

		sc.Scan()
		strS := strings.Fields(sc.Text())

		S := make([]int, len(strS))
		for i, v := range strS {
			S[i], _ = strconv.Atoi(v)
		}

		solve(N, S)
	}
}

func solve(N int, S []int) {
	sort.Slice(S, func(i, j int) bool {
		if i == 0 || j == len(S)-1 {
			return true
		}
		if j == 0 || i == len(S)-1 {
			return false
		}
		return S[i] < S[j]
	})

	// ドミノ1を選ぶのは確定
	count := 1
	pre := S[0]
	for i := 1; i < N-1; i++ {
		// ドミノiを選ぶ条件
		// - preがドミノiを倒せること
		if 2*pre < S[i] {
			break
		}

		// - preがドミノi+1を倒せないこと
		if S[i+1] <= 2*pre {
			continue
		}

		// - preがドミノNを倒せないこと
		if S[len(S)-1] <= 2*pre {
			break
		}

		pre = S[i]
		count++
	}

	// ドミノNを選べるかどうかの判定
	if S[len(S)-1] <= 2*pre {
		fmt.Println(count + 1)
	} else {
		fmt.Println(-1)
	}
}

Submission Info

Judge Result