CF2261F2.Plegma II: Ask Me Any Cell (Hard Version)

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Note the unusual score distribution for F1 and F2. This problem is significantly more difficult than F1.

There is a visualizer available for this problem. You can view it using this link.

Hacks are disabled on this problem.

This is the Hard Version of the problem. The only difference between the two versions is the constraints on nn and kk.

Verity has a grid of nn rows and nn columns. The rows are numbered from 11 to nn from top to bottom, and the columns are numbered from 11 to nn from left to right. The cell on row pp and column qq is denoted by (p,q)(p, q).

Verity also has a robot, Circuity, with extremely simple functionality. Verity must program Circuity so it can automatically locate specific cells on the grid, while ensuring these cells stay hidden from foreign robots.

There are two phases in this problem.

Phase 1: Verity (Encoding)

In this phase, Verity tries to encode a given cell on the grid.

Verity receives a target cell (r,c)(r, c), and he assigns a binary value (00 or 11) to each cell of the grid. On cells with value 11, beacons that broadcast signal will be placed, while cells with value 00 remain empty.

However, he believes that using too few beacons will make it easy for foreigners to also locate the target cell. Therefore, he has decided that it is safest to use at most kk zeros.

Phase 2: Circuity (Decoding)

In this phase, Circuity tries to find the cell Verity encoded, based on the grid he created. However, Circuity is unable to process large grids efficiently.

At each moment of time, Circuity suspects that the target cell lies in the subgrid bounded by the two cells (x0,y0)(x_0, y_0) and (x1,y1)(x_1, y_1). Initially, (x0,y0)=(1,1)(x_0, y_0) = (1, 1) and (x1,y1)=(n,n)(x_1, y_1) = (n, n).

Circuity locates the encoded cell by making exactly 2n−22n-2 decisions, one after another. Each decision works as follows.

Circuity can sense the number of beacons in the current subgrid. Let this number be SS. Formally, SS is the number of cells with value 11 inside the subgrid bounded by the cells (x0,y0)(x_0, y_0) and (x1,y1)(x_1, y_1).

Based solely on SS, it will choose exactly one of the following actions:

  • Action U: increase x0x_0 by 11
  • Action L: increase y0y_0 by 11
  • Action D: decrease x1x_1 by 11
  • Action R: decrease y1y_1 by 11

Note that this decision does not rely on previous decisions, and it cannot directly rely on the values of x0,x1,y0x_0, x_1, y_0 or y1y_1. Circuity is memoriless, and the only parameter when making a decision must be SS in the current moment.

If at any point x0>x1x_0 \gt x_1 or y0>y1y_0 \gt y_1, the program bugs out and Circuity is unsuccessful.

The cell Verity encoded in this grid was some cell (r,c)(r, c). After all 2n−22n-2 decisions, it must hold that x0=x1=rx_0 = x_1 = r and y0=y1=cy_0 = y_1 = c.

There are exactly 32 tests:

  • Each value n=3,10,11,…,40n = 3,10,11,\ldots,40 is used in exactly one test, in order.
  • For every allowed nn, k=f(n)k=f(n), where f(n)f(n) is the minimum possible worst-case number of zeros needed to encode any cell of an n×nn \times n grid.

注意 F1 和 F2 的非常规分值分布。本题明显比 F1 更难。

本题提供一个可视化工具。您可通过此链接查看。

本题禁用 Hack 功能。

本题为该问题的困难版本(Hard Version)。两个版本之间唯一的区别在于对 nn 和 kk 的约束条件不同。

Verity 拥有一个 nn 行 nn 列的网格。行从上到下编号为 11 至 nn,列从左到右编号为 11 至 nn。第 pp 行第 qq 列的格子记作 (p,q)(p, q)。

Verity 还拥有一台名为 Circuity 的机器人,其功能极为简单。Verity 必须对 Circuity 进行编程,使其能自动定位网格中特定的格子,同时确保这些格子对其他外部机器人保持隐藏。

本题分为两个阶段:

第一阶段:Verity(编码)

在此阶段,Verity 尝试对给定的网格格子进行编码。

Verity 接收一个目标格子 (r,c)(r, c),并为网格中的每个格子分配一个二进制值(00 或 11)。值为 11 的格子上将放置广播信号的信标,而值为 00 的格子则保持空置。

然而,Verity 认为使用过少的信标会使外部机器人也容易定位目标格子。因此,他决定最安全的做法是至多使用 kk 个零。

第二阶段:Circuity(解码)

在此阶段,Circuity 基于 Verity 所构建的网格尝试找出被编码的目标格子。但 Circuity 无法高效处理大型网格。

在任意时刻,Circuity 怀疑目标格子位于由两个格子 (x0,y0)(x_0, y_0) 和 (x1,y1)(x_1, y_1) 所界定的子网格内。初始时,(x0,y0)=(1,1)(x_0, y_0) = (1, 1),(x1,y1)=(n,n)(x_1, y_1) = (n, n)。

Circuity 通过恰好执行 2n−22n-2 次决策(依次进行)来定位被编码的格子。每次决策的工作方式如下:

Circuity 可感知当前子网格中信标的数量。记该数量为 SS。形式化地,SS 即子网格(由格子 (x0,y0)(x_0, y_0) 和 (x1,y1)(x_1, y_1) 界定)内值为 11 的格子个数。

Circuity 仅依据当前的 SS 值,严格选择以下四种操作之一:

  • U 操作:将 x0x_0 增加 11
  • L 操作:将 y0y_0 增加 11
  • D 操作:将 x1x_1 减少 11
  • R 操作:将 y1y_1 减少 11

注意:该决策不依赖于此前的任何决策,也不能直接依赖 x0,x1,y0x_0, x_1, y_0 或 y1y_1 的值。Circuity 是无记忆的,其做决策时唯一允许的参数只能是当前时刻的 SS 值。

若在任一时刻出现 x0>x1x_0 > x_1 或 y0>y1y_0 > y_1,程序将崩溃,Circuity 定位失败。

Verity 在该网格中所编码的目标格子为某个格子 (r,c)(r, c)。经过全部 2n−22n-2 次决策后,必须满足 x0=x1=rx_0 = x_1 = r 且 y0=y1=cy_0 = y_1 = c。

本题共包含恰好 32 组测试数据:

  • 每个 n=3,10,11,…,40n = 3,10,11,\ldots,40 的取值恰好在一组测试中使用,且按此顺序排列;
  • 对于每个允许的 nn,均有 k=f(n)k=f(n),其中 f(n)f(n) 表示在 n×nn \times n 网格中对任意格子进行编码所需的、最坏情况下最少的零的个数。

输入格式

The only input contains one integer nn (n=3n = 3 or 10≤n≤4010 \le n \le 40).

唯一输入包含一个整数 nn(n=3n = 3 或 10≤n≤4010 \le n \le 40)。

输出格式

  • For Phase 11:

Output n2n^2 binary grids.

The ii-th grid is the grid Verity should choose when the target is (r,c)(r, c), where r=⌊i−1n⌋+1r = \lfloor \frac{i-1}{n} \rfloor + 1 and c=((i−1) mod n)+1c = ((i-1) \bmod n) + 1.

In other words, the first grid corresponds to target (1,1)(1,1), the second grid corresponds to target (1,2)(1,2), the (n+1)(n+1)-th grid corresponds to target (2,1)(2,1), and so on.

Each grid must contain at most k=f(n)k=f(n) zeros.

  • For Phase 22:

Output a sequence of n2+1n^2 + 1 characters: a0,a1,a2,…,an2a_0, a_1, a_2, \ldots, a_{n^2}. Each character must be one of U, D, L, or R. The ii-th character means that if S=iS=i, then Circuity performs action aia_i.

  • 第一阶段:

输出 n2n^2 个二进制网格。

第 ii 个网格是当目标位置为 (r,c)(r, c) 时 Verity 应选择的网格,其中 r=⌊i−1n⌋+1r = \lfloor \frac{i-1}{n} \rfloor + 1,c=((i−1) mod n)+1c = ((i-1) \bmod n) + 1。

换言之,第一个网格对应目标 (1,1)(1,1),第二个网格对应目标 (1,2)(1,2),第 (n+1)(n+1) 个网格对应目标 (2,1)(2,1),依此类推。

每个网格中最多包含 k=f(n)k=f(n) 个零。

  • 第二阶段:

输出一个长度为 n2+1n^2 + 1 的字符序列:a0,a1,a2,…,an2a_0, a_1, a_2, \ldots, a_{n^2}。每个字符必须是 U、D、L 或 R 中的一个。第 ii 个字符表示:若 S=iS=i,则 Circuity 执行动作 aia_i。

输入输出样例

  • 输入#1

    3

    输出#1

    111
    111
    001
    
    011
    111
    100
    
    110
    110
    110
    
    010
    111
    111
    
    111
    111
    111
    
    010
    111
    101
    
    111
    111
    110
    
    111
    011
    111
    
    011
    010
    111
    
    DURLDULRUU

说明/提示

Consider the third grid as an example. The target cell is (1,3)(1,3).

Verity chooses the following grid:

110110110

The action sequence is:

DURLDULRUU

Initially, Circuity examines the subgrid bounded by (1,1)(1,1) and (3,3)(3,3).

It must locate cell (1,3)(1,3), so it will make 2⋅3−2=42 \cdot 3 - 2 = 4 decisions.

  • Decision 1: there are S=6S=6 ones in the current subgrid, so Circuity performs action a6=La_6=\mathtt{L}.

    The new subgrid becomes [(1,2),(3,3)][(1,2),(3,3)].

  • Decision 2: there are S=3S=3 ones in the current subgrid, so Circuity performs action a3=La_3=\mathtt{L}.

    The new subgrid becomes [(1,3),(3,3)][(1,3),(3,3)].

  • Decision 3: there are S=0S=0 ones in the current subgrid, so Circuity performs action a0=Da_0=\mathtt{D}.

    The new subgrid becomes [(1,3),(2,3)][(1,3),(2,3)].

  • Decision 4: there are again S=0S=0 ones in the current subgrid, so Circuity performs action a0=Da_0=\mathtt{D}.

    The new subgrid becomes [(1,3),(1,3)][(1,3),(1,3)].

After all decisions, Circuity ends up at cell (1,3)(1,3), which is indeed the target cell.

以第三个网格为例,目标单元格为 (1,3)(1,3)。

Verity 选择了如下网格:

110110110

对应的操作序列为:

DURLDULRUU

初始时,Circuity 检查由 (1,1)(1,1) 和 (3,3)(3,3) 所界定的子网格。

它必须定位单元格 (1,3)(1,3),因此将做出 2⋅3−2=42 \cdot 3 - 2 = 4 次决策。

  • 决策 1:当前子网格中包含 S=6S=6 个 1,因此 Circuity 执行操作 a6=La_6=\mathtt{L}。

    新的子网格变为 [(1,2),(3,3)][(1,2),(3,3)]。

  • 决策 2:当前子网格中包含 S=3S=3 个 1,因此 Circuity 执行操作 a3=La_3=\mathtt{L}。

    新的子网格变为 [(1,3),(3,3)][(1,3),(3,3)]。

  • 决策 3:当前子网格中包含 S=0S=0 个 1,因此 Circuity 执行操作 a0=Da_0=\mathtt{D}。

    新的子网格变为 [(1,3),(2,3)][(1,3),(2,3)]。

  • 决策 4:当前子网格中再次包含 S=0S=0 个 1,因此 Circuity 执行操作 a0=Da_0=\mathtt{D}。

    新的子网格变为 [(1,3),(1,3)][(1,3),(1,3)]。

在完成全部决策后,Circuity 最终停留在单元格 (1,3)(1,3),这确实是目标单元格。

输入解题思路,AI测评打分。不知道怎么写?

首页