#P11277. 世界沉睡童话

世界沉睡童话

背景

$$\begin{array}{cr} \text{时针停在相互拥抱的前一秒}\\ \text{凝视每件事的空白}\\ \text{等待缝隙}\overset{\text{Memory Limit Exceeded}}{\text{被缺失章节填满}}\\ \text{等}\overset{\text{return }{\color{#EE0000}0}\text{;}}{{\color{#EE0000}\text{某个人}}\text{回来}}\\ &\text{——《世界沉睡童话》} \end{array}$$


在不断变化着的世界中,找出彼此的所属。

压缩成一个数的记忆,泠珞又能否还原呢?

题目描述

给定正整数 nn 和非负整数 kk,请构造一个正整数序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,满足恰有 kk 组正整数对 (i,j)(i,j) (1≤i<j≤n)(1\le i<j\le n),满足 max⁡(ai,aj)\max(a_i,a_j) 是 min⁡(ai,aj)\min(a_i,a_j) 的倍数。

输入保证有解。

为了获得满分,你需要保证 ai≤2n−1a_i\le 2n-1。

输入格式

第一行两个非负整数 n,kn,k。输入保证有解。

输出格式

一行 nn 个正整数,第 ii 个表示你构造的 aia_i。

为了获得满分,你需要保证 ai≤2n−1a_i\le 2n-1。

输出任意一组可行解均可。

6 8
3 6 1 4 2 5
3 3
5 5 5

提示

【样例 #1 解释】

符合要求的数对有 (1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(3,6),(4,5)(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(3,6),(4,5) 共 k=8k=8 组。

【数据范围】

本题采用捆绑测试和子任务依赖。

本题中,RE 会显示为 UKE,这是正常现象。

具体地,部分测试点可能属于多个子任务。因此,子任务不会显式地显示出来。以下表格表示了每个测试点属于的子任务情况:

测试点编号 所属子任务
1,2,4,81,2,4,8 1,2,3,4,51,2,3,4,5
2222 2,3,4,52,3,4,5
4343 3,4,53,4,5
3,5,6,9∼11,15∼183,5,6,9\sim11,15\sim18 1,2,4,51,2,4,5
7,12∼14,19∼217,12\sim 14,19\sim 21 1,2,51,2,5
23∼25,33,3923\sim25,33,39 2,4,52,4,5
26∼32,34∼38,40∼4226\sim 32,34\sim 38,40\sim 42 2,52,5
44∼5444\sim 54 4,54,5
55∼10055\sim 100 55

不保证不存在某些数据符合它不在的 Subtask 的条件。

对于 100%100\% 的数据,1≤n≤2.5×1051\le n\le 2.5\times10^5,0≤k≤n(n−1)20\le k\le \dfrac{n(n-1)}{2},本题的数据保证有解。

对于每个子任务,如果你保证了 ai≤4na_i\le 4n,你将获得 p1p_1 的分数。如果你保证了 ai≤3na_i\le 3n,你将获得 p2p_2 的分数。如果你保证了 ai≤2n−1a_i\le 2n-1,你将获得 p3p_3 的分数,即满分。

对于每个子任务,你只有保证了所有属于它的测试点都保证了以上的条件,你才能获得对应的分数。

输出任意一组符合要求的可行解都可以获得对应的分数。

因此,您无法直接知道每个子任务的 p1,p2p_1,p_2 部分分数的获取情况。你可以通过在程序内进行 assert(用法:assert(表达式),若表达式为 0 / false 则会 RE)确认自己的通过情况。

子任务编号 p1p_1 p2p_2 p3p_3 n≤n\le k≤k\le
11 22 33 55 n(n−1)2\dfrac{n(n-1)}{2}
22 55 1111 1717 10410^4
33 11 22 2.5×1052.5\times10^5 00
44 77 1313 2929 n−1n-1
55 1111 2323 4747 n(n−1)2\dfrac{n(n-1)}{2}