QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #305496 | #8004. Bit Component | yyyyxh | AC ✓ | 75ms | 9104kb | C++23 | 2.2kb | 2024-01-15 14:25:17 | 2024-01-15 14:25:18 |
Judging History
answer
#include <set>
#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>
#define ALL(vc) (vc).begin(),(vc).end()
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
bool flag=0;
vector<int> cons(int n){
set<int> st;
st.emplace(0);
int cur=0;
vector<int> res;
for(int i=1;i<=n;++i){
int tmp=0;
if(cur) tmp=__lg(cur)+1;
bool fl=1;
for(int t=tmp-1;~t;--t)
if(st.find(cur^(1<<t))==st.end()){
fl=0;cur^=(1<<t);break;
}
if(fl) cur^=(1<<tmp);
st.emplace(cur);
res.emplace_back(cur);
}
return res;
}
int main(){
int n=read();
int mx=__lg(n)+1;
if(n==(1<<mx)-1){
puts("YES");
vector<int> res=cons(n);
for(int x:res) printf("%d ",x);
putchar('\n');
return 0;
}
if(n<=12){puts("NO");return 0;}
if(~n>>(mx-2)&1){puts("NO");return 0;}
if(n==(1<<(mx-1))+(1<<(mx-2))){puts("NO");return 0;}
puts("YES");
if(n==(1<<(mx-1))+1+(1<<(mx-2))){
vector<int> arr1=cons((1<<(mx-1))-1);
vector<int> arr2=cons((1<<(mx-2))-1);
auto it1=find(ALL(arr1),(1<<(mx-1))-1);
auto it2=find(ALL(arr1),(1<<(mx-1))-2);
if(mx&1) swap(*it1,*it2);
for(int &x:arr2) x+=(1<<(mx-1));
int tmp=(1<<(mx-1))+(1<<(mx-2));
vector<int> res;
for(int x:arr1) res.emplace_back(x);
res.emplace_back(tmp+1);
reverse(arr1.begin(),arr1.end());
for(int x:arr2){
int t=x-(1<<(mx-1));
if(t!=1&&t!=0&&t+tmp<=n) res.emplace_back(t+tmp);
res.emplace_back(x);
}
res.emplace_back((1<<(mx-1)));
res.emplace_back(tmp);
for(int x:res) printf("%d ",x);
putchar('\n');
}
else{
vector<int> arr1=cons((1<<(mx-1))-1);
vector<int> arr2=cons((1<<(mx-2))-1);
for(int &x:arr2) x+=(1<<(mx-1));
int tmp=(1<<(mx-1))+(1<<(mx-2));
vector<int> res;
for(int x:arr1) res.emplace_back(x);
res.emplace_back(tmp+2);
reverse(arr2.begin(),arr2.end());
for(int x:arr2){
int t=x-(1<<(mx-1));
if(t!=2&&t!=0&&t+tmp<=n) res.emplace_back(t+tmp);
res.emplace_back(x);
}
res.emplace_back((1<<(mx-1)));
res.emplace_back(tmp);
for(int x:res) printf("%d ",x);
putchar('\n');
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3028kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 2836kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3040kb
input:
3
output:
YES 1 3 2
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 1ms
memory: 2796kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 2760kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 2784kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 0ms
memory: 3108kb
input:
7
output:
YES 1 3 2 6 4 5 7
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 1ms
memory: 2756kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 2764kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 0ms
memory: 2700kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 1ms
memory: 2772kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 1ms
memory: 2796kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: 0
Accepted
time: 0ms
memory: 2992kb
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: 1ms
memory: 3252kb
input:
14
output:
YES 1 3 2 6 4 5 7 14 10 11 13 9 8 12
result:
ok answer is 1
Test #15:
score: 0
Accepted
time: 1ms
memory: 3252kb
input:
15
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14
result:
ok answer is 1
Test #16:
score: 0
Accepted
time: 0ms
memory: 2768kb
input:
16
output:
NO
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 0ms
memory: 2728kb
input:
17
output:
NO
result:
ok answer is 0
Test #18:
score: 0
Accepted
time: 0ms
memory: 2756kb
input:
23
output:
NO
result:
ok answer is 0
Test #19:
score: 0
Accepted
time: 0ms
memory: 2924kb
input:
24
output:
NO
result:
ok answer is 0
Test #20:
score: 0
Accepted
time: 0ms
memory: 3028kb
input:
25
output:
YES 1 3 2 6 4 5 7 14 11 9 13 12 8 10 15 25 17 19 18 22 20 21 23 16 24
result:
ok answer is 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 3032kb
input:
26
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 26 23 21 20 22 18 19 25 17 16 24
result:
ok answer is 1
Test #22:
score: 0
Accepted
time: 0ms
memory: 3064kb
input:
27
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 26 23 21 20 22 18 27 19 25 17 16 24
result:
ok answer is 1
Test #23:
score: 0
Accepted
time: 0ms
memory: 2792kb
input:
40
output:
NO
result:
ok answer is 0
Test #24:
score: 0
Accepted
time: 0ms
memory: 3120kb
input:
53
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 50 46 42 40 44 45 41 43 47 39 53 37 52 36 38 34 51 35 49 33 32 48
result:
ok answer is 1
Test #25:
score: 0
Accepted
time: 0ms
memory: 2784kb
input:
93
output:
NO
result:
ok answer is 0
Test #26:
score: 0
Accepted
time: 0ms
memory: 3028kb
input:
105
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 98 95 87 83 91 89 81 85 93 92 84 80 88 90 82 86 94 78 74 104 72 76 77 105 73 75 79 103 71 101 69 100 68 102 70 66 99...
result:
ok answer is 1
Test #27:
score: 0
Accepted
time: 0ms
memory: 2764kb
input:
132
output:
NO
result:
ok answer is 0
Test #28:
score: 0
Accepted
time: 0ms
memory: 3092kb
input:
221
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #29:
score: 0
Accepted
time: 0ms
memory: 2820kb
input:
373
output:
NO
result:
ok answer is 0
Test #30:
score: 0
Accepted
time: 1ms
memory: 3068kb
input:
473
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #31:
score: 0
Accepted
time: 0ms
memory: 2912kb
input:
513
output:
NO
result:
ok answer is 0
Test #32:
score: 0
Accepted
time: 1ms
memory: 3080kb
input:
934
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #33:
score: 0
Accepted
time: 0ms
memory: 2792kb
input:
1356
output:
NO
result:
ok answer is 0
Test #34:
score: 0
Accepted
time: 1ms
memory: 3148kb
input:
1651
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #35:
score: 0
Accepted
time: 0ms
memory: 2920kb
input:
2263
output:
NO
result:
ok answer is 0
Test #36:
score: 0
Accepted
time: 0ms
memory: 3128kb
input:
3330
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #37:
score: 0
Accepted
time: 0ms
memory: 2784kb
input:
4375
output:
NO
result:
ok answer is 0
Test #38:
score: 0
Accepted
time: 2ms
memory: 3252kb
input:
7989
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #39:
score: 0
Accepted
time: 0ms
memory: 2828kb
input:
10925
output:
NO
result:
ok answer is 0
Test #40:
score: 0
Accepted
time: 2ms
memory: 3440kb
input:
14097
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #41:
score: 0
Accepted
time: 0ms
memory: 2832kb
input:
16893
output:
NO
result:
ok answer is 0
Test #42:
score: 0
Accepted
time: 8ms
memory: 3952kb
input:
28913
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #43:
score: 0
Accepted
time: 0ms
memory: 2764kb
input:
40092
output:
NO
result:
ok answer is 0
Test #44:
score: 0
Accepted
time: 16ms
memory: 4564kb
input:
54980
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #45:
score: 0
Accepted
time: 0ms
memory: 2704kb
input:
88104
output:
NO
result:
ok answer is 0
Test #46:
score: 0
Accepted
time: 31ms
memory: 5908kb
input:
106284
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #47:
score: 0
Accepted
time: 1ms
memory: 2920kb
input:
152797
output:
NO
result:
ok answer is 0
Test #48:
score: 0
Accepted
time: 75ms
memory: 9104kb
input:
200000
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #49:
score: 0
Accepted
time: 1ms
memory: 3356kb
input:
3073
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #50:
score: 0
Accepted
time: 5ms
memory: 3864kb
input:
16383
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #51:
score: 0
Accepted
time: 11ms
memory: 4588kb
input:
32767
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #52:
score: 0
Accepted
time: 1ms
memory: 3108kb
input:
399
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Test #53:
score: 0
Accepted
time: 0ms
memory: 2768kb
input:
5757
output:
NO
result:
ok answer is 0
Test #54:
score: 0
Accepted
time: 0ms
memory: 2732kb
input:
179
output:
NO
result:
ok answer is 0
Test #55:
score: 0
Accepted
time: 1ms
memory: 3116kb
input:
228
output:
YES 1 3 2 6 4 5 7 15 11 9 13 12 8 10 14 30 22 18 26 24 16 20 28 29 21 17 25 27 19 23 31 63 47 39 55 51 35 43 59 57 41 33 49 53 37 45 61 60 44 36 52 48 32 40 56 58 42 34 50 54 38 46 62 126 94 78 110 102 70 86 118 114 82 66 98 106 74 90 122 120 88 72 104 96 64 80 112 116 84 68 100 108 76 92 124 125 93...
result:
ok answer is 1
Extra Test:
score: 0
Extra Test Passed