#agc043e. [agc043_e]Topology

[agc043_e]Topology

给定正整数 N(1N8)N (1\leq N \leq 8)以及一个长度为 2N2^N0101 序列 A0,A1,,A2N1A_0,A_1, \cdots ,A_{2^N-1}(保证 A0=1A_0=1)。判断是否存在一条闭合曲线 CC,它对于所有的 2N2^N 个集合 S{0,1,,N1}S \subseteq \{0,1, \cdots ,N-1\} 都满足以下条件:

  • x=iS2ix=\sum_{i \in S} 2^iBSB_S 是点集 {(i+0,5,0,5)iS}\{(i+0,5,0,5) \mid i \in S\}
  • Ax=1A_x=1,则存在一种方法连续地移动闭曲线 CC ,使得移动后的 CC 上的任意一点的 yy 坐标都为负,且在此过程中 CC 不碰到 BSB_S
  • Ax=0A_x=0,则不存在这样一种方法。

CC 是一条闭曲线,当且仅当:

  • CC 是一个连续函数 C:[0,1]R2C: [0,1] \rightarrow \mathbb{R}^2,满足 C(0)=C(1)C(0)=C(1)

我们称一条闭曲线 CC 能够被连续地移动,且在此过程中不碰到点集 XX,最终成为一条闭曲线 DD,当且仅当:

  • 存在一个函数 f:[0,1]×[0,1]R2f:[0,1] \times [0,1] \rightarrow \mathbb{R}^2 满足以下条件:
    • ff 是连续的。
    • f(0,t)=C(t)f(0,t)=C(t)
    • f(1,t)=D(t)f(1,t)=D(t)
    • f(x,t)∉Xf(x,t) \not\in X

若存在这样的 CC,请构造一条这样的 CC 并输出,格式是:

先输出一个整数 LL,需满足 0L2500000\leq L \leq 250000

接下来的 L+1L+1 行,每行两个整数 x,yx,y,表示你构造的闭曲线 CC 是一条依次经过这 LL 个点的多边形,需满足:

  • 0xiN0\leq x_i \leq N0yi10\leq y_i \leq 1,且 xi,yix_i,y_i 是整数,其中 0iL0\leq i \leq L
  • xixi+1+yiyi+1=1|x_i-x_{i+1}|+|y_i-y_{i+1}|=1,其中 0iL10\leq i \leq L-1
  • (x0,y0)=(xL,yL)(x_0,y_0)=(x_L,y_L)

可以证明,如果存在一条闭曲线满足题目中的要求,那么也存在一条闭曲线能够用这种方式表示出来。