#P7264. Mirror

Mirror

题目背景

Mirror

And it’s not the voice of all the others

You’ve only said it to yourself

I know what you want from me, from me

I know what you’re thinking

题目描述

Porter Robinson: We all have these avatars that we give to our critical inner voices - we might imagine a scornful parent telling us we’ll fail, or a critic telling us our work comes up short, or a society telling us that we aren’t good enough - it’s about recognizing that most of this criticism is self-inflicted.

Mivik 在镜中看见了自己的 Inner Voice ——不过是在一个镜子般对称的迷宫中。这个迷宫很特殊:它有无穷多行和无穷多列,行和列都从 00 开始标号。一个格子 (i,j)(i,j) 能通过(没有障碍)当且仅当 (i&j)=0(i\&j)=0,其中 &\& 指按位与运算(Bitwise And,百度百科)。下图给出了这个迷宫的 0630\sim63 行和 0630\sim 63 列的图像:

迷宫

Mivik 想抓到并消灭那个给予自己负面声音的 Inner Voice,但他找不到路了。Mivik 和 Inner Voice 最初处在迷宫中的两点。Mivik 想知道,在 Mivik 的 Inner Voice 一直不移动的情况下,他至少需要走过多少个方格才能抓到他的 Inner Voice(Mivik 的起始格不算)。

但是... 游戏并不会像 Mivik 想象的一样简单。邪恶的 ggy 在这个迷宫中的某些格子布下了许多炸弹,Mivik 需要拆除它们才能踏上这些格子。Mivik 需要你告诉他,在他走过的方格数最少的情况下,他至少需要拆除哪些炸弹。

请注意炸弹可能会重合,而你只有拆除一个格子上的所有炸弹才能通过这个格子。保障炸弹不与起点重合。

输入格式

第一行一个整数 nn,代表 ggy 设下的炸弹个数。

接下来 nn 行,其中的ii 行两个非负整数,代表 ii 号炸弹的坐标(从 1 开始编号)。

接下来一行两个非负整数 sxsxsysy,代表 Mivik 位于哪一行哪一列。

接下来一行两个非负整数 exexeyey,代表 Mivik 的 Inner Voice 位于哪一行哪一列。

输出格式

第一行一个整数,代表 Mivik 至少需要走少格才能抓到他的 Inner Voice。

接下来一行,给出一个长度为 nn 的 01 串,第 ii 个字符为 1 代表 Mivik 必须拆除第 ii 号炸弹,0 代表不需要。

0
0 0
0 2
2

3
0 0
0 2
1 2
4 2
3 4
13
110
0
12 34
3 100
85

提示

样例解释

样例一:显然由于没有任何炸弹,Mivik 向右走两格就能抓到他的 Inner Voice。

样例二:Mivik 的最短路径如图所示:

路径

其中,图片左上角为 (0,0)(0,0),蓝色代表 Mivik 的起始位置,绿色代表 Inner Voice 的位置,红色代表 Mivik 的最短路径,黄色代表炸弹,橙色(其实是黄色 + 红色)代表 Mivik 必须拆除的炸弹。

数据范围

对于全部数据,有 1n21051\le n\le 2\cdot 10^5(sx,sy)(ex,ey)(sx,sy)\ne(ex,ey),并保证对于给出的任何坐标 (x,y)(x,y) 都有 x&y=0x\&y=00x,y10180\le x,y\le 10^{18}

Subtask 1 (10 pts):保证 Mivik 可以直线(只向 上/下/左/右 走)抓到他的 Inner Voice。

Subtask 2 (15 pts):保证 sx=sy=0sx=sy=0

Subtask 3 (20 pts):保证 0(任意 x,y 坐标)1000\le(\text{任意 x,y 坐标})\le 100

Subtask 4 (25 pts):保证 n=0n=0

Subtask 5 (30 pts):无特殊限制。