1059C.md (1534B)
1 Source: https://codeforces.com/problemset/problem/1059/C 2 3 C. Sequence Transformation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let's call the following process a transformation of a sequence of length $n$. 22 23 If the sequence is empty, the process ends. Otherwise, append the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) (GCD) of all the elements of the sequence to the result and remove one arbitrary element from the sequence. Thus, when the process ends, we have a sequence of $n$ integers: the greatest common divisors of all the elements in the sequence before each deletion. 24 25 You are given an integer sequence $1, 2, \dots, n$. Find the lexicographically maximum result of its transformation. 26 27 A sequence $a_1, a_2, \ldots, a_n$ is lexicographically larger than a sequence $b_1, b_2, \ldots, b_n$, if there is an index $i$ such that $a_j = b_j$ for all $j \lt i$, and $a_i \gt b_i$. 28 29 Input 30 31 The first and only line of input contains one integer $n$ ($1\le n\le 10^6$). 32 33 Output 34 35 Output $n$ integers — the lexicographically maximum result of the transformation. 36 37 Examples 38 39 Input 40 41 ``` 42 3 43 ``` 44 45 Output 46 47 ``` 48 1 1 3 49 ``` 50 51 Input 52 53 ``` 54 2 55 ``` 56 57 Output 58 59 ``` 60 1 2 61 ``` 62 63 Input 64 65 ``` 66 1 67 ``` 68 69 Output 70 71 ``` 72 1 73 ``` 74 75 Note 76 77 In the first sample the answer may be achieved this way: 78 79 * Append GCD$(1, 2, 3) = 1$, remove $2$. 80 * Append GCD$(1, 3) = 1$, remove $1$. 81 * Append GCD$(3) = 3$, remove $3$. 82 83 We get the sequence $[1, 1, 3]$ as the result.