QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305965 | #8004. Bit Component | ckiseki | AC ✓ | 6ms | 5748kb | C++20 | 1.8kb | 2024-01-16 06:37:35 | 2024-01-16 06:37:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
vector<int> f(int n) {
// cerr << "n = " << n << endl;
if (n == 7) {
return {1, 3, 2, 6, 4, 5, 7};
}
if (n == 15) {
return {1, 3, 2, 6, 4, 5, 7, 13, 9, 11, 10, 8, 12, 14, 15};
}
int k = 1;
while (k*2 <= n) k *= 2;
// cerr << "k = " << k << endl;
if (n <= k / 2 * 3) {
return {};
}
auto A = f(k - 1);
auto B = f(k/2 - 1);
vector<int> res = A;
int U = k*2 - 1;
for (int x: B) {
int u = x | k;
int v = u | (k/2);
// cerr << "u = " << u << ' ' << bitset<5>(u) << endl;
// cerr << "v = " << v << ' ' << bitset<5>(v) << endl;
if (v != U && v <= n) res.push_back(v);
if (u != k + 1) res.push_back(u);
}
res.push_back(k + 1);
res.push_back(k);
if ((k | (k/2)) <= n) res.push_back(k | (k/2));
if (U <= n) res.push_back(U);
return res;
}
int main() {
cin.tie(0) -> sync_with_stdio(false);
int n;
cin >> n;
if (n == 1) {
cout << "YES\n1\n";
return 0;
}
if (n == 3) {
cout << "YES\n2 3 1\n";
return 0;
}
auto res = f(n);
if (n == 13 || n == 14) {
res = f(15);
res.resize(n);
}
if (res.empty()) {
cout << "NO\n";
return 0;
}
cout << "YES\n";
for (int x: res) {
cout << x << ' ';
/* cout << x << '\t';
for (int i = 0; i < 20; i++)
cout << " #"[(x >> i & 1)];
cout << endl; */
}
/* set<int> st(res.begin(), res.end());
for (int i = 1; i <= n; i++)
if (!st.count(i))
cerr << "i = " << i << endl;
cerr << res.size() << endl; */
cout << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3
output:
YES 2 3 1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
7
output:
YES 1 3 2 6 4 5 7
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
13
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12
result:
ok answer is 1
Test #14:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
14
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14
result:
ok answer is 1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
15
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15
result:
ok answer is 1
Test #16:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
16
output:
NO
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
17
output:
NO
result:
ok answer is 0
Test #18:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
23
output:
NO
result:
ok answer is 0
Test #19:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
24
output:
NO
result:
ok answer is 0
Test #20:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
25
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 19 18 22 20 21 23 17 16 24
result:
ok answer is 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
26
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 19 26 18 22 20 21 23 17 16 24
result:
ok answer is 1
Test #22:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
27
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 22 20 21 23 17 16 24
result:
ok answer is 1
Test #23:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
40
output:
NO
result:
ok answer is 0
Test #24:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
53
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 38 52 36 53 37 39 45 41 43 42 40 44 46 47 33 32 48
result:
ok answer is 1
Test #25:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
93
output:
NO
result:
ok answer is 0
Test #26:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
105
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 77 105 73 75 74 104 72 76 78 79 89 91 83 90 82 94 86 92 84 93 85 87 81 80...
result:
ok answer is 1
Test #27:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
132
output:
NO
result:
ok answer is 0
Test #28:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
221
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #29:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
373
output:
NO
result:
ok answer is 0
Test #30:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
473
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #31:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
513
output:
NO
result:
ok answer is 0
Test #32:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
934
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #33:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1356
output:
NO
result:
ok answer is 0
Test #34:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
1651
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #35:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2263
output:
NO
result:
ok answer is 0
Test #36:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
3330
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #37:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
4375
output:
NO
result:
ok answer is 0
Test #38:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
7989
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #39:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
10925
output:
NO
result:
ok answer is 0
Test #40:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
14097
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #41:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
16893
output:
NO
result:
ok answer is 0
Test #42:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
28913
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #43:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
40092
output:
NO
result:
ok answer is 0
Test #44:
score: 0
Accepted
time: 3ms
memory: 3776kb
input:
54980
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #45:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
88104
output:
NO
result:
ok answer is 0
Test #46:
score: 0
Accepted
time: 5ms
memory: 4356kb
input:
106284
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #47:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
152797
output:
NO
result:
ok answer is 0
Test #48:
score: 0
Accepted
time: 6ms
memory: 5748kb
input:
200000
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #49:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
3073
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #50:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
16383
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #51:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
32767
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #52:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
399
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Test #53:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5757
output:
NO
result:
ok answer is 0
Test #54:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
179
output:
NO
result:
ok answer is 0
Test #55:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
228
output:
YES 1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...
result:
ok answer is 1
Extra Test:
score: 0
Extra Test Passed