結果
問題 | No.1588 Connection |
ユーザー | ccppjsrb |
提出日時 | 2021-07-08 23:09:17 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 3,304 bytes |
コンパイル時間 | 12,516 ms |
コンパイル使用メモリ | 206,932 KB |
実行使用メモリ | 24,348 KB |
平均クエリ数 | 551.84 |
最終ジャッジ日時 | 2023-09-24 11:32:54 |
合計ジャッジ時間 | 15,854 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
23,952 KB |
testcase_01 | AC | 25 ms
23,532 KB |
testcase_02 | AC | 25 ms
23,976 KB |
testcase_03 | AC | 26 ms
23,316 KB |
testcase_04 | AC | 25 ms
23,316 KB |
testcase_05 | AC | 26 ms
23,796 KB |
testcase_06 | AC | 26 ms
23,952 KB |
testcase_07 | AC | 26 ms
23,460 KB |
testcase_08 | AC | 28 ms
23,976 KB |
testcase_09 | AC | 29 ms
23,520 KB |
testcase_10 | AC | 29 ms
23,316 KB |
testcase_11 | AC | 30 ms
23,964 KB |
testcase_12 | AC | 61 ms
23,520 KB |
testcase_13 | AC | 69 ms
24,300 KB |
testcase_14 | AC | 26 ms
24,276 KB |
testcase_15 | AC | 27 ms
23,472 KB |
testcase_16 | AC | 26 ms
24,024 KB |
testcase_17 | AC | 25 ms
23,784 KB |
testcase_18 | AC | 24 ms
23,376 KB |
testcase_19 | AC | 25 ms
24,324 KB |
testcase_20 | AC | 27 ms
23,352 KB |
testcase_21 | AC | 112 ms
23,520 KB |
testcase_22 | AC | 113 ms
24,000 KB |
testcase_23 | AC | 59 ms
24,024 KB |
testcase_24 | AC | 42 ms
23,952 KB |
testcase_25 | AC | 69 ms
23,428 KB |
testcase_26 | AC | 66 ms
24,348 KB |
testcase_27 | AC | 44 ms
24,336 KB |
testcase_28 | AC | 38 ms
23,352 KB |
testcase_29 | AC | 107 ms
23,340 KB |
testcase_30 | AC | 107 ms
24,324 KB |
testcase_31 | AC | 24 ms
23,640 KB |
ソースコード
package main import ( "bufio" "fmt" "io" "math/rand" "os" "strconv" "time" ) var iost *Iost type Iost struct { Scanner *bufio.Scanner Writer *bufio.Writer } func NewIost(fp io.Reader, wfp io.Writer) *Iost { const BufSize = 2000005 scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, BufSize), BufSize) return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)} } func (i *Iost) Text() string { if !i.Scanner.Scan() { panic("scan failed") } return i.Scanner.Text() } func (i *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x } func (i *Iost) GetNextInt() int { return i.Atoi(i.Text()) } func (i *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x } func (i *Iost) GetNextInt64() int64 { return i.Atoi64(i.Text()) } func (i *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x } func (i *Iost) GetNextFloat64() float64 { return i.Atof64(i.Text()) } func (i *Iost) Print(x ...interface{}) { fmt.Fprint(i.Writer, x...) } func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) } func (i *Iost) Println(x ...interface{}) { fmt.Fprintln(i.Writer, x...) } func isLocal() bool { return os.Getenv("I") == "IronMan" } func main() { fp := os.Stdin wfp := os.Stdout if isLocal() { fp, _ = os.Open(os.Getenv("END_GAME")) } iost = NewIost(fp, wfp) defer func() { if isLocal() { iost.Println(recover()) } iost.Writer.Flush() }() solve() for i := 0; isLocal() && i < 100; i++ { iost.Println("-----------------------------------") solve() } } func solve() { rand.Seed(time.Now().UnixNano()) n := iost.GetNextInt() m := iost.GetNextInt() if isLocal() { testdata = makeGrid(n, n) bb := rand.Perm(n*n - 2) rand.Shuffle(n*n-2, func(i, j int) { bb[i], bb[j] = bb[j], bb[i] }) for mm := 0; mm < m-2; mm++ { testdata[(bb[mm]+1)/n][(bb[mm]+1)%n] = 1 } testdata[0][0] = 1 testdata[n-1][n-1] = 1 for i := 0; i < n; i++ { iost.Println(testdata[i]) } } g := makeGrid(n, n) const ( Unknown = iota Black White ) q := make([][2]int, 0) q = append(q, [2]int{0, 0}) dy := [4]int{-1, 0, 0, 1} dx := [4]int{0, -1, 1, 0} for i := 0; i < 3000 && len(q) > 0; i++ { p := q[0] q = q[1:] g[p[0]][p[1]] = 1 m-- if p[0] == n-1 && p[1] == n-1 { iost.Println("Yes") return } if m == 0 { break } for d := 0; d < 4; d++ { y := p[0] + dy[d] x := p[1] + dx[d] if y < 0 || y >= n { continue } if x < 0 || x >= n { continue } if g[y][x] == Unknown { switch ask(y, x) { case "-1": return case "Black": q = append(q, [2]int{y, x}) g[y][x] = 1 case "White": g[y][x] = 2 } } } } iost.Println("No") } var testdata [][]int func ask(y, x int) string { if isLocal() { if testdata[y][x] == 1 { return "Black" } return "White" } iost.Println(fmt.Sprintf("%d %d", y+1, x+1)) iost.Writer.Flush() return iost.Text() } func makeGrid(h, w int) [][]int { index := make([][]int, h, h) data := make([]int, h*w, h*w) for i := 0; i < h; i++ { index[i] = data[i*w : (i+1)*w] } return index }