codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1988C.md (1350B)


      1 Source: https://codeforces.com/problemset/problem/1988/C
      2 
      3 C. Increasing Sequence with Fixed OR
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a positive integer $n$. Find the longest sequence of positive integers $a=[a_1,a_2,\ldots,a_k]$ that satisfies the following conditions, and print the sequence:
     22 
     23 * $a_i\le n$ for all $1\le i\le k$.
     24 * $a$ is strictly increasing. That is, $a_i \gt a_{i-1}$ for all $2\le i\le k$.
     25 * $a_i\,|\,a_{i-1}=n$ for all $2\le i\le k$, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.
     30 
     31 The only line of each test case contains one integer $n$ ($1\le n\le 10^{18}$).
     32 
     33 It's guaranteed that the sum of lengths of the longest valid sequences does not exceed $5\cdot 10^5$.
     34 
     35 Output
     36 
     37 For each testcase, print two lines. In the first line, print the length of your constructed sequence, $k$. In the second line, print $k$ positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 1
     47 
     48 3
     49 
     50 14
     51 
     52 23
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 1
     59 1
     60 3
     61 1 2 3
     62 4
     63 4 10 12 14
     64 5
     65 7 18 21 22 23
     66 ```