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 n and k.
Verity has a grid of n rows and n columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to n from left to right. The cell on row p and column q is denoted by (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), and he assigns a binary value (0 or 1) to each cell of the grid. On cells with value 1, beacons that broadcast signal will be placed, while cells with value 0 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 k 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) and (x1,y1). Initially, (x0,y0)=(1,1) and (x1,y1)=(n,n).
Circuity locates the encoded cell by making exactly 2n−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 S. Formally, S is the number of cells with value 1 inside the subgrid bounded by the cells (x0,y0) and (x1,y1).
Based solely on S, it will choose exactly one of the following actions:
- Action U: increase x0 by 1
- Action L: increase y0 by 1
- Action D: decrease x1 by 1
- Action R: decrease y1 by 1
Note that this decision does not rely on previous decisions, and it cannot directly rely on the values of x0,x1,y0 or y1. Circuity is memoriless, and the only parameter when making a decision must be S in the current moment.
If at any point x0>x1 or y0>y1, the program bugs out and Circuity is unsuccessful.
The cell Verity encoded in this grid was some cell (r,c). After all 2n−2 decisions, it must hold that x0=x1=r and y0=y1=c.
There are exactly 32 tests:
- Each value n=3,10,11,…,40 is used in exactly one test, in order.
- For every allowed n, k=f(n), where f(n) is the minimum possible worst-case number of zeros needed to encode any cell of an n×n grid.
注意 F1 和 F2 的非常规分值分布。本题明显比 F1 更难。
本题提供一个可视化工具。您可通过此链接查看。
本题禁用 Hack 功能。
本题为该问题的困难版本(Hard Version)。两个版本之间唯一的区别在于对 n 和 k 的约束条件不同。
Verity 拥有一个 n 行 n 列的网格。行从上到下编号为 1 至 n,列从左到右编号为 1 至 n。第 p 行第 q 列的格子记作 (p,q)。
Verity 还拥有一台名为 Circuity 的机器人,其功能极为简单。Verity 必须对 Circuity 进行编程,使其能自动定位网格中特定的格子,同时确保这些格子对其他外部机器人保持隐藏。
本题分为两个阶段:
第一阶段:Verity(编码)
在此阶段,Verity 尝试对给定的网格格子进行编码。
Verity 接收一个目标格子 (r,c),并为网格中的每个格子分配一个二进制值(0 或 1)。值为 1 的格子上将放置广播信号的信标,而值为 0 的格子则保持空置。
然而,Verity 认为使用过少的信标会使外部机器人也容易定位目标格子。因此,他决定最安全的做法是至多使用 k 个零。
第二阶段:Circuity(解码)
在此阶段,Circuity 基于 Verity 所构建的网格尝试找出被编码的目标格子。但 Circuity 无法高效处理大型网格。
在任意时刻,Circuity 怀疑目标格子位于由两个格子 (x0,y0) 和 (x1,y1) 所界定的子网格内。初始时,(x0,y0)=(1,1),(x1,y1)=(n,n)。
Circuity 通过恰好执行 2n−2 次决策(依次进行)来定位被编码的格子。每次决策的工作方式如下:
Circuity 可感知当前子网格中信标的数量。记该数量为 S。形式化地,S 即子网格(由格子 (x0,y0) 和 (x1,y1) 界定)内值为 1 的格子个数。
Circuity 仅依据当前的 S 值,严格选择以下四种操作之一:
- U 操作:将 x0 增加 1
- L 操作:将 y0 增加 1
- D 操作:将 x1 减少 1
- R 操作:将 y1 减少 1
注意:该决策不依赖于此前的任何决策,也不能直接依赖 x0,x1,y0 或 y1 的值。Circuity 是无记忆的,其做决策时唯一允许的参数只能是当前时刻的 S 值。
若在任一时刻出现 x0>x1 或 y0>y1,程序将崩溃,Circuity 定位失败。
Verity 在该网格中所编码的目标格子为某个格子 (r,c)。经过全部 2n−2 次决策后,必须满足 x0=x1=r 且 y0=y1=c。
本题共包含恰好 32 组测试数据:
- 每个 n=3,10,11,…,40 的取值恰好在一组测试中使用,且按此顺序排列;
- 对于每个允许的 n,均有 k=f(n),其中 f(n) 表示在 n×n 网格中对任意格子进行编码所需的、最坏情况下最少的零的个数。
输入格式
The only input contains one integer n (n=3 or 10≤n≤40).
唯一输入包含一个整数 n(n=3 或 10≤n≤40)。
输出格式
- For Phase 1:
Output n2 binary grids.
The i-th grid is the grid Verity should choose when the target is (r,c), where r=⌊ni−1⌋+1 and c=((i−1)modn)+1.
In other words, the first grid corresponds to target (1,1), the second grid corresponds to target (1,2), the (n+1)-th grid corresponds to target (2,1), and so on.
Each grid must contain at most k=f(n) zeros.
- For Phase 2:
Output a sequence of n2+1 characters: a0,a1,a2,…,an2. Each character must be one of U, D, L, or R. The i-th character means that if S=i, then Circuity performs action ai.
- 第一阶段:
输出 n2 个二进制网格。
第 i 个网格是当目标位置为 (r,c) 时 Verity 应选择的网格,其中 r=⌊ni−1⌋+1,c=((i−1)modn)+1。
换言之,第一个网格对应目标 (1,1),第二个网格对应目标 (1,2),第 (n+1) 个网格对应目标 (2,1),依此类推。
每个网格中最多包含 k=f(n) 个零。
- 第二阶段:
输出一个长度为 n2+1 的字符序列:a0,a1,a2,…,an2。每个字符必须是 U、D、L 或 R 中的一个。第 i 个字符表示:若 S=i,则 Circuity 执行动作 ai。
输入输出样例
输入#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).
Verity chooses the following grid:
110110110
The action sequence is:
DURLDULRUU
Initially, Circuity examines the subgrid bounded by (1,1) and (3,3).
It must locate cell (1,3), so it will make 2⋅3−2=4 decisions.
-
Decision 1: there are S=6 ones in the current subgrid, so Circuity performs action a6=L.
The new subgrid becomes [(1,2),(3,3)].
-
Decision 2: there are S=3 ones in the current subgrid, so Circuity performs action a3=L.
The new subgrid becomes [(1,3),(3,3)].
-
Decision 3: there are S=0 ones in the current subgrid, so Circuity performs action a0=D.
The new subgrid becomes [(1,3),(2,3)].
-
Decision 4: there are again S=0 ones in the current subgrid, so Circuity performs action a0=D.
The new subgrid becomes [(1,3),(1,3)].
After all decisions, Circuity ends up at cell (1,3), which is indeed the target cell.
以第三个网格为例,目标单元格为 (1,3)。
Verity 选择了如下网格:
110110110
对应的操作序列为:
DURLDULRUU
初始时,Circuity 检查由 (1,1) 和 (3,3) 所界定的子网格。
它必须定位单元格 (1,3),因此将做出 2⋅3−2=4 次决策。
-
决策 1:当前子网格中包含 S=6 个 1,因此 Circuity 执行操作 a6=L。
新的子网格变为 [(1,2),(3,3)]。
-
决策 2:当前子网格中包含 S=3 个 1,因此 Circuity 执行操作 a3=L。
新的子网格变为 [(1,3),(3,3)]。
-
决策 3:当前子网格中包含 S=0 个 1,因此 Circuity 执行操作 a0=D。
新的子网格变为 [(1,3),(2,3)]。
-
决策 4:当前子网格中再次包含 S=0 个 1,因此 Circuity 执行操作 a0=D。
新的子网格变为 [(1,3),(1,3)]。
在完成全部决策后,Circuity 最终停留在单元格 (1,3),这确实是目标单元格。
输入解题思路,AI测评打分。不知道怎么写?