結果

問題 No.1149 色塗りゲーム
コンテスト
ユーザー ID 21712
提出日時 2026-06-06 16:19:27
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 3,116 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,931 ms
コンパイル使用メモリ 279,484 KB
実行使用メモリ 29,924 KB
平均クエリ数 19.88
最終ジャッジ日時 2026-06-06 16:19:59
合計ジャッジ時間 20,880 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	solve(Judge{})
}

type Interactive interface {
	N() int
	Q(k1,x1 int) (t, k2, x2 int)
}

type Judge struct{}

func (Judge) N() int {
	var n int
	Scan(&n)
	return n
}

func (Judge) Q(k1, x1 int) (t, k2, x2 int) {
	Println(k1, x1)
	Scan(&t)
	if t == 2 || t == 3 {
		Scan(&k2, &x2)
	}
	return
}

func solve(io Interactive) {
	var k1,x1,h int
	n := io.N()
	if n == 1 {
		k1, x1 = 1, 1
	} else if n == 2 {
		k1, x1 = 2, 1
	} else if n % 2 == 0 {
		k1, x1 = 2, n/2
		h = n/2+1
	} else {
		k1, x1 = 1, n/2+1
		h = n/2+1
	}
	for {
		t, k2, x2 := io.Q(k1, x1)
		if t != 3 {
			return
		}
		k1 = k2
		if x2 < h {
			x1 = x2+h
		} else {
			x1 = x2-h
		}
	}
}

func init() {
	check()
}

type Testcase struct {
	n int
	field []bool
	ac,wa,debug  bool
}

func (tc *Testcase) N() int {
	if tc.debug {
		println("N()")
	}
	return tc.n
}
func (tc *Testcase) Q(k1, x1 int) (t, k2, x2 int) {
	if tc.debug {
		println("Q(", k1, ",",x1,")")
	}
	if tc.wa || tc.ac {
		panic("wrong")
	}
	if k1 != 1 && k1 != 2 {
		println("n=",tc.n)
		println("k1=",k1)
		tc.wa = true
		t = 1
		return
	}
	if !(1 <= x1 && x1 <= tc.n + 1 - k1) {
		println("n=",tc.n)
		println("x1=",x1)
		tc.wa = true
		t = 1
		return
	}
	x1--
	if tc.field[x1] || tc.field[x1+k1-1] {
		println("n=",tc.n)
		println("k1=",k1)
		println("x1=",x1+1)
		println("field[x1:x1+k1]=",Sprint(tc.field[x1:x1+k1]))
		tc.wa = true
		t = 1
		return
	}
	tc.field[x1] = true
	tc.field[x1+k1-1] = true
	if tc.debug {
		println("field=",Sprint(tc.field))
	}
	kx := []int{}
	for i := 0; i < tc.n; i++ {
		if !tc.field[i] {
			kx = append(kx, (i+1)*10+1)
			if i+1<tc.n && !tc.field[i+1] {
				kx = append(kx, (i+1)*10+2)
			}
		}
	}
	if len(kx) == 0 {
		tc.ac = true
		return
	}
	if len(kx) == 1 {
		tc.wa = true
		t = 2
		k2, x2 = kx[0]%10, kx[0]/10
		return
	}
	if len(kx) == 2 && kx[0]/10 == kx[1]/10 {
		tc.wa = true
		t = 2
		k2, x2 = 2,kx[0]/10
		return
	}
	t = 3
	k2, x2 = kx[0]%10, kx[0]/10
	for i, v := range kx {
		j := v%len(kx)
		if (i+1)*(j+1)%2 == 0 {
			k2, x2 = v%10, v/10
		}
	}
	tc.field[x2-1] = true
	tc.field[x2-1+k2-1] = true
	if tc.debug {
		println("t=",t,",k=",k2,",x=",x2)
		println("field=",Sprint(tc.field))
	}
	return
}

func check() {
	for n := 1; n <= 100; n++ {
		tc := &Testcase{
			n: n,
			field: make([]bool, n),
			ac: false,
			wa: false,
			debug: n == 3,
		}
		solve(tc)
		if tc.wa {
			panic("wrong")
		} else if !tc.ac {
			println("n=",n)
			println("f=",Sprint(tc.field))
			panic("not ac")
		}
	}
}


/*
考察

適当に脳内シミュレーションしてみた結果
N <= 2なら先手全取り
N >= 3なら
Nの真ん中をとって同数の2区画に分ける
あとは相手が取ったのとミラーするように反対側を同じようにとる
すると先手必勝


例 N = 9
.........
....A....
.B..A....
.B..A.A..
.B..ABA..
AB..ABA..
AB..ABABB
ABAAABABB

例 N = 10
..........
....AA....
BB..AAAA..
BB..AAAA.B
BB.AAAAA.B
BBBAAAAA.B
BBBAAAAAAB

初手で真ん中以外をとったとき
相手がどういう動きするのかわからんので
シミュレーションできんな

*/
0