#2200. T2

    ID: 2200 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1650来源:qoj.ac数据:公开样例构造

T2

T2

题目描述

标题: T2 - Problem - QOJ.ac

#8369. T2

Statistics

The problem was used in the following contests:

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

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

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

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

输入格式

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

输出格式

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

第二行 2n+1−1 个数,其中第 i 个数表示 i 号点染成的颜色 ci。

样例输入 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≤n≤20,12≤k≤1.1×106。

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

子任务 2(8 分):k=1.1×106。

子任务 3(15 分):k=6×105。

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1 12
2
2 2 1

样例 2

2 12
3
2 3 2 1 3 2 3