結果

問題 No.1149 色塗りゲーム
コンテスト
ユーザー anagohirame
提出日時 2020-08-07 23:15:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 201 ms / 2,000 ms
コード長 1,076 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,536 KB
実行使用メモリ 86,452 KB
平均クエリ数 19.06
最終ジャッジ日時 2024-07-17 05:15:23
合計ジャッジ時間 9,613 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import exit
n = int(input())
grundy = [0 for _ in range(n+1)]
grundy[1] = 1
#grundy[2] = 2
for i in range(2, n+1):
	g = set()
	for j in range(i):
		g.add(grundy[j] ^ grundy[i-j-1])
		if j < i-1:
			g.add(grundy[j] ^ grundy[i-j-2])
	x = 0
	while x in g:
		x += 1
	grundy[i] = x
#print(grundy)

def calc(b):
	g = 0
	tmp = 0
	for i in range(n+1):
		if b[i]:
			tmp += 1
		else:
			g ^= grundy[tmp]
			tmp = 0
	#print(b, g)
	#print("#####")
	return g

def cop(b, k, x):
	res = [True for _ in range(n+1)]
	res[n] = False
	for i in range(n):
		if (not b[i]) or x <= i < x+k:
			res[i] = False
	return res

a = [True for _ in range(n+1)]
a[n] = False
while True:
	for i in range(n):
		if a[i]:
			c = cop(a, 1, i)
			if calc(c) == 0:
				print(1, i+1, flush=True)
				a[i] = False
				break
		if a[i] and a[i+1]:
			c = cop(a, 2, i)
			if calc(c) == 0:
				print(2, i+1, flush=True)
				a[i], a[i+1] = False, False
				break
	e = int(input())
	if e <= 1:
		exit()
	elif e == 2:
		input()
		exit()
	k, x = map(int, input().split())
	a[x-1], a[x+k-2] = False, False
	#print(a)
0