from collections import deque
from sys import setrecursionlimit
import heapq
def score(grid):
n = len(grid)
m = len(grid[0])
res = 0
for i in range(n):
cnt = 0
for j in range(m):
cnt += (grid[i][j] == 1)
res += cnt > m//2
for j in range(m):
cnt = 0
for i in range(n):
cnt += (grid[i][j] == 0)
res += cnt > n//2
return res
def solveGeneral(n: int, m: int, r: int): # r -> number of rows we sacrifice
grid = [[1] * m for _ in range(n)]
q = []
for i in range(n-r): heapq.heappush(q, (0, i))
for i in range(n-r, n):
for j in range(m): grid[i][j] = 0
j = 0
cur = 0
res = n-1
rem = []
limit = (n-r)/2
while j < m:
cnt, i = heapq.heappop(q)
if cnt >= (m-1)//2: break
grid[i][j] = 0
heapq.heappush(q, (cnt+1, i))
cur += 1
if cur > limit:
cur = 0
j += 1
res += 1
return (res, grid)
def solve():
n, m = map(int, input().split(" "))
res = -1
cur = [[1] * m for _ in range(n)]
for r in range(n):
s, g = solveGeneral(n, m, r)
if s > res:
res = s
cur = g
print(res)
for row in cur:
for c in row:
print("+" if c else "-", end = "")
print()
"""
11
+-+-+-++-+
-++-+-++-+
-+-++-+-++
+--+-++-++
----------
"""
for _ in range(int(input())): solve()
Compilation message (stdout)
Compiling 'stones.py'...
=======
adding: __main__.pyc (deflated 44%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |