Submission #1205772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205772		ofoz	Red-blue table (IZhO19_stones)	Pypy 3	0 / 100	2101 ms	157056 KiB

stones

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-r
    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
    
    if n >= m and n >= res:
        grid = [[1] * m for _ in range(n)]
        res = n

    if m >= n and m >= res:
        grid = [[0] * m for _ in range(n)] 
        res = m

    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 49%)

=======

• Subtask 1: 0 / 17
• Subtask 2: 0 / 10
• Subtask 3: 0 / 16
• Subtask 4: 0 / 11
• Subtask 5: 0 / 15
• Subtask 6: 0 / 31