QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 8369. T2

Statistics

小 T 有一个 $n+1$ 层的满二叉树 $T$。具体来说,这棵树以 $1$ 为根,共有 $2^{n+1}-1$ 个结点。对于每个点 $x$ $(1\leq x < 2^n)$,它的左儿子和右儿子分别为 $2x$ 和 $2x+1$。

有一天,树 $T$ 上每两个相邻的叶子 $y$ 和 $y+1$ $(2^n\leq y\leq 2^{n+1}-2)$ 之间都连了一条边。小 T 对它非常失望,因为它不再是一棵真正的树了。小 T 想到他刚刚学过图论中的缩点,于是他决定应用自己的知识来让它重新变成一棵树。

具体来说,小 T 首先需要决定他所用的颜色数 $m$,接着他要给每个点 $i$ 染上一种颜色 $c_i$ $(1\leq c_i\leq m)$。之后建立一张 $m$ 个点的新图 $G$,$G$ 中两点 $i,j$ $(i\neq j)$ 有边当且仅当 $T$ 中存在两个相连的点 $u,v$ 满足 $c_u=i,\ c_v=j$。小 T 要求图 $G$ 必须是一棵树。

为了更加美观,小 T 希望每种颜色至少有 $1$ 个点使用,且至多有 $k$ 个点使用。你能否帮助他构造出想要的方案呢?

输入格式

一行两个数 $n,k$,分别表示满二叉树层数和每种颜色的数量限制。

输出格式

第一行一个数 $m$ 表示使用的颜色数。

第二行 $2^{n+1}-1$ 个数,其中第 $i$ 个数表示 $i$ 号点染成的颜色 $c_i$。

样例输入 1

1 12

样例输出 1

2
2 2 1

样例输入 2

2 12

样例输出 2

3
2 3 2 1 3 2 3

样例解释

样例 $1$ 中图 $G$ 有 $2$ 个点,有 $1$ 条边 $(1,2)$,边 $(1,2)$ 对应 $T$ 的边 $(1,3),(2,3)$。

样例 $2$ 中图 $G$ 有 $3$ 个点,有 $2$ 条边 $(1,3),(3,2)$,边 $(1,3)$ 对应 $T$ 的边 $(4,2),(4,5)$,边 $(3,2)$ 对应 $T$ 的边 $(2,1),(5,6),(3,7),(6,7)$。

数据范围

对于所有数据,$1\leq n\leq 20$,$12\leq k \leq 1.1\times 10^6$。

子任务 $1$($11$ 分):$n\leq 4$,$k=12$。

子任务 $2$($8$ 分):$k=1.1\times 10^6$。

子任务 $3$($15$ 分):$k=6\times 10^5$。

子任务 $4$($16$ 分):$k=5000$。

子任务 $5$($15$ 分):$k=200$。

子任务 $6$($35$ 分):$k=12$。