Light show 2
After solving the problem Light Show, you realize that the glaring white light can be used to illuminate certain squares in the grid. In this problem, you are given which squares should shine white and which should not, and your task is to place the lamps along the edge so that as many of the requirements as possible are met.
Input
The input consists of $10$ test cases.
-
The first line contains an integer $T$ ($0 \leq T \leq 10$), the number of the test case ($0$ is the example case below).
-
The second line contains two integers: $n$ and $m$ ($1 \le n, m \le 1000$), the number of rows and columns in the grid.
-
The following $n$ lines describe which squares should shine white and which should not. Each line will consist of a string with $m$ ones and zeros. A one in row $r$ and column $c$ indicates that the square should shine white. A zero indicates that the square should not shine white.
Output
Print four lines with a string on each. The strings should represent a placement of lamps in the same format as the input in Light Show. Note that you should not print $n$ and $m$.
Points
Your program will be tested on $10$ test cases and scored based on how it performs relative to the judges’ solution.
A solution’s score for a specific test case is defined as $\max (0, x - \frac{nm}{2})$, where $x$ is the number of squares in the grid where the light from the lamps placed by the solution meets the given requirements for which squares should shine white and which should not. If your solution scored $P_1$ and the judges’ solution scored $P_2$, you get $10 \cdot (P_1 / P_2)$ points for the test case, rounded to two decimal places.
Your score for a submission is the sum of the scores for the test cases, and your total score is the score of the best submission. Thus, you cannot combine test cases between different submissions, but you must submit a single program that maximizes your score on all test cases simultaneously.
Your solution can receive a maximum of $100$ points, even if it is better than the judges’ solution.
The example test case will always give $0$ points.
Explanation of Sample 1
In the example case, the solution meets all the requirements and its score is therefore $7.5$, which is the maximum possible.
Test Cases
Here are descriptions of the $10$ test cases that occur. Test cases of type 1 have been generated by taking the result of a random placement of lamps. There is therefore always a way to achieve the maximum $\frac{nm}{2}$ points on these test cases. Test cases of type 2 have been generated by randomly assigning each square to be a one or zero with $50\% $ probability. These test cases often have no solution that meets all the requirements.
|
Test Case |
Limits |
Type |
|
$1$ |
$n = 10$, $m = 10$ |
1 |
|
$2$ |
$n = 40$, $m = 40$ |
1 |
|
$3$ |
$n = 150$, $m = 150$ |
1 |
|
$4$ |
$n = 400$, $m = 400$ |
1 |
|
$5$ |
$n = 1000$, $m = 1000$ |
1 |
|
$6$ |
$n = 100$, $m = 10$ |
1 |
|
$7$ |
$n = 1000$, $m = 1$ |
1 |
|
$8$ |
$n = 10$, $m = 10$ |
2 |
|
$9$ |
$n = 100$, $m = 100$ |
2 |
|
$10$ |
$n = 1000$, $m = 1000$ |
2 |
| Sample Input 1 | Sample Output 1 |
|---|---|
0 3 5 00110 10101 10001 |
RRBBR RBB GRGBG GRB |
