101 . 獨一無二的區間和(ㄏㄢˋ)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (28/28)

Submission's AC Ratio

43.3% (29/67)

Tags

ioicamp ioicamp-2023

Description

給定正整數 N，判斷是否存在長度為 N 的序列 [a1,a2,…,aN](0≤ai<230) 使得任意非空區間 [al,al+1,…,ar](1≤l≤r≤N) 的位元和(ㄏㄢˋ)和(ㄏㄜˊ) (bitwise AND sum) 是獨一無二的。如果有，請構造任意滿足這個條件的序列。

換句話說，集合
S={al&al+1&⋯&ar∣l,r∈N,1≤l≤r≤N}
的大小必須是 (N+12)。

Input Format

每份測試檔案的第一行（也是唯一一行）會包含恰一個整數N，代表需要構造的序列長度。

  • 1≤N≤5000

Output Format

對於每筆測試資料，如果可以構造出滿足條件的序列，第一行請輸出 Yes；反之輸出 No。

如果第一行的輸出是為 Yes，請輸出第二行 a1,a2,…,aN 代表你所構造出來的序列。兩兩整數之間以半形空白分開。

Sample Input 1

1

Sample Output 1

Yes
80000000

Sample Input 2

3

Sample Output 2

Yes
525277394 749578766 471847610

Hints

Problem Source

IOICamp 2023 Day2 pA

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~25 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
Submit
Back to Top