The table (Codeforces 226D)
Tags: Greedy, constructive algorithms

Harry Potter has a difficult homework. Given a rectangular table, consisting of n × m cells. Each cell of the table contains the integer. Harry knows how to use two spells: the first spell change the sign of the integers in the selected row, the second — in the selected column. Harry's task is to make non-negative the sum of the numbers in each row and each column using these spells.Alone, the boy can not cope. Help the young magician!

Input: The first line contains two integers n and m (1 ≤ n,  m ≤ 100) — the number of rows and the number of columns. Next n lines follow, each contains m integers: j-th integer in the i-th line is ai, j (|ai, j| ≤ 100), the number in the i-th row and j-th column of the table.The rows of the table numbered from 1 to n. The columns of the table numbered from 1 to m.

Output: In the first line print the number a — the number of required applications of the first spell. Next print a space-separated integers — the row numbers, you want to apply a spell. These row numbers must be distinct!In the second line print the number b — the number of required applications of the second spell. Next print b space-separated integers — the column numbers, you want to apply a spell. These column numbers must be distinct!If there are several solutions are allowed to print any of them.


Sample Inputs:
4 1
-1
-1
-1
-1

2 4
-1 -1 -1 2
1 1 1 1

Sample Outputs:
4 1 2 3 4
0

1 1
1 4

Solution (Python):
import math
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(n):
    a[i] = [int(_) for _ in input().split()]
row = []
col = []
rowStat = [1] * n
colStat = [1] * m
while True:
    bad = False
    for i in range(n):
        total = 0
        for j in range(m):
            total += a[i][j]
        if total < 0:
            bad = True
            rowStat[i] *= -1
            for j in range(m):
                a[i][j] *= -1
    for i in range(m):
        total = 0
        for j in range(n):
            total += a[j][i]
        if total < 0:
            bad = True
            colStat[i] *= -1
            for j in range(n):
                a[j][i] *= -1
    if not bad:
        break
for i in range(n):
    if rowStat[i] == -1:
        row.append(i + 1)
for i in range(m):
    if colStat[i] == -1:
        col.append(i + 1)
print(len(row), ' '.join(map(str, row)))
print(len(col), ' '.join(map(str, col)))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sint = lambda : int(input())
mint = lambda : map(int, input().split())
ints = lambda : list(map(int, input().split()))

def solve() -> None:
    (n, m) = mint()
    g = []
    for _ in range(n):
        g.append(ints())
    row = [0] * n
    col = [0] * m
    for (i, r) in enumerate(g):
        for (j, x) in enumerate(r):
            row[i] += x
            col[j] += x
    (ro, co) = ([0] * n, [0] * m)
    while min(row) < 0 or min(col) < 0:
        for i in range(n):
            if row[i] < 0:
                row[i] = -row[i]
                ro[i] ^= 1
                for j in range(m):
                    col[j] -= g[i][j] * 2
                    g[i][j] = -g[i][j]
        for j in range(m):
            if col[j] < 0:
                col[j] = -col[j]
                co[j] ^= 1
                for i in range(n):
                    row[i] -= g[i][j] * 2
                    g[i][j] = -g[i][j]
    print(sum(ro), *(i + 1 for (i, v) in enumerate(ro) if v))
    print(sum(co), *(i + 1 for (i, v) in enumerate(co) if v))
solve()

Solution (Python):
(n, m) = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(list(map(int, input().split())))
f_x = [0] * n
f_y = [0] * m
sum_x = [0] * n
sum_y = [0] * m
for i in range(n):
    for j in range(m):
        sum_x[i] += grid[i][j]
        sum_y[j] += grid[i][j]
while min(sum_x) < 0 or min(sum_y) < 0:
    for i in range(n):
        if sum_x[i] < 0:
            f_x[i] ^= 1
            sum_x[i] = -sum_x[i]
            for j in range(m):
                sum_y[j] -= grid[i][j] * 2
                grid[i][j] = -grid[i][j]
    for i in range(m):
        if sum_y[i] < 0:
            f_y[i] ^= 1
            sum_y[i] = -sum_y[i]
            for j in range(n):
                sum_x[j] -= grid[j][i] * 2
                grid[j][i] = -grid[j][i]
print(sum(f_x), *(i + 1 for i in range(n) if f_x[i]))
print(sum(f_y), *(i + 1 for i in range(m) if f_y[i]))