問題一覧 > スコア問題

No.5002 stick xor

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 88
作問者 : mai
お気に入りにしたユーザー ProblemId : 2174 / 自分の提出
問題文最終更新日: 2022-05-15 17:32:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder long contest 1 (順位表) の他の問題:

Note from the Organizers

The contest is scheduled to end at 2018-06-01 22:00:00. It is unrated.
After a submission, unless its result is CE, you cannot submit again for 5 minutes.
We apologize for the inconvenience, but for the rankings, please refer to the score order tab above rather than the contest standings.

Problem Statement

There is a grid of size $N\times N$. Each cell of the grid is painted either pure white or jet black.
For the cell $(y,x)$, which is the $y$-th from the top and the $x$-th from the left, $A_{y,x} = 0$ if it is pure white and $A_{y,x} = 1$ if it is jet black.

You perform $K$ operations on this grid.
In the $i$-th operation, you choose a rectangle within the grid with height $L_i$ and width $1$, or with height $1$ and width $L_i$ (that is, either vertical or horizontal),
and flip the cells in the rectangular region: pure white cells become jet black and jet black cells become pure white.

Let $W_0$ be the number of pure white cells before the operations and $W_K$ be the number of pure white cells after the $K$ operations. Your points are then $W_K-W_0$.
Find a placement of the rectangles that makes your points as high as possible.

Since this is a score-based problem, you do not need to find an optimal solution.

Your score is the sum of the points over all test cases. There are 32 test cases.

Input

$N$ $K$
$L_1$ $\ldots$ $L_K$
$A_{1,1}$ $\ldots$ $A_{1,N}$
$\ldots$
$A_{N,1}$ $\ldots$ $A_{N,N}$

$N = 60$
$K = 500$
$1 \le L_i \le 25$
$A_{i,j} \in \{0,1\}$

All values are integers.
There are no separators, such as spaces, between $A_{i,j}$ and $A_{i,k}$.

Test Case Generation

All test cases are randomly generated. There are no artificial test cases (such as an entirely white grid).

  • Each $L_i$ is chosen with equal probability from the values satisfying the constraints.
  • Each cell is generated as a jet black cell with probability 1/2.
For details, please refer to the generator.

Output

$a_1$ $b_1$ $c_1$ $d_1$
$\ldots$
$a_K$ $b_K$ $c_K$ $d_K$

$1 \le a_i \le c_i \le N$
$1 \le b_i \le d_i \le N$
Either $a_i=c_i, d_i-b_i+1=L_i$ or $b_i=d_i, c_i-a_i+1=L_i$ must be satisfied.


Output $K$ lines.
The $i$-th line means that the rectangle $長方形(a_i,b_i,c_i,d_i)$ is chosen for the $i$-th operation.
Here, the rectangle $長方形(a,b,c,d)$ is the set of cells $\{(y,x)|a\le y\le c,b \le x\le d\}$.


This is a score-based problem.
Any output that satisfies the format gets AC, but please aim for as high a score as possible.

Visualizer

The visualizer is available here

Note: Please end your standard output with a newline. Otherwise, it may not work.
2018/05/26 10:26 It now works with or without a trailing newline.

Sample

Sample 1
Input
3 3
2 1 3
001
110
000

This input does not satisfy the problem's constraints, so it is not included in the test cases. It also does not work in the visualizer.


Sample Output
1 3 2 3
2 1 2 1
2 1 2 3

After the 1st operation, the grid is in the following state.

000
111
000
After the 2nd operation, the grid is in the following state.
000
011
000
After the 3rd operation, the grid is in the following state.
000
100
000
The number of pure white cells has increased from the original 6 to 8, so you get 2 points.

Sample 2(gen_case1.txt)
Input

It is available on Github Gist.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。