This problem can be solved using hill climbing. (The following explanation can be read without prior knowledge of hill climbing.)

Define \(X\) and \(Y\) as the sets of people in rooms X and Y, respectively. Also, define the score \(f(X,Y)\) for the room assignment \((X,Y)\) as follows:

\(f(X,Y) = \sum_{i,j ∈ X} A_{ij} + \sum_{i,j ∈ Y} A_{ij}\).

Intuitively, the higher the score, the more people are in a good state. Here, we consider improving the score.

If we choose one person who is not in a good state and move them to the other room, the score increases by at least \(1\). We repeat this operation as long as it can be performed. When the operation can no longer be performed, it means all \(N\) people are in a good state. Therefore, we should output the state at that point. Since the score has an upper bound, the operation terminates in a finite number of steps.

The range of the score is roughly \(\pm \sum |A_{i,j}|\) at most. If we perform differential updates with each operation, each operation can be done in \(O(N)\), so the overall time complexity is \(O(N^3 \max A)\).
It is also acceptable to spend \(O(N^2)\) time per update for a total of \(O(N^4 \max A)\).