QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #586955 | #8004. Bit Component | ucup-team3519# | AC ✓ | 11ms | 5672kb | C++20 | 1.9kb | 2024-09-24 16:46:02 | 2024-09-24 16:46:02 |
Judging History
answer
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=500005;
const ll mod=998244353;
int G(int x){
return x^(x>>1);
}
vector<int>ans7={7,5,4,6,2,3,1};
vector<int>ans;
vector<int>follow[N];
void fill(int carry,int l,int r){
if(l<=r){
for(int i=l;i<=r;i++){
ans.push_back(carry^G(i));
}
}
else{
for(int i=l;i>=r;i--){
ans.push_back(carry^G(i));
}
}
}
void op(int x){
vector<int>rlans;
if(x==0){
cout<<"NO\n";
return;
}
cout<<"YES\n";
for(int i=0;i<ans.size();i++){
ll p=ans[i];
// cout<<p<<' ';
rlans.push_back(p);
for(int j=0;j<follow[p].size();j++){
rlans.push_back(follow[p][j]);
//cout<<follow[p][j]<<' ';
}
}
// cout<<rlans.size()<<'\n';
for(int i=0;i<rlans.size();i++){
// for(int j=10;j>=0;j--){
// if(rlans[i]&(1<<j)){
// cout<<1;
// }
// else{
// cout<<0;
// }
// }
// cout<<'\n';
cout<<rlans[i]<<' ';
}
return;
}
void solve(){
int n;
cin>>n;
if(n<=7){
if(n==1){
ans={1};
op(1);
}
else if(n==3){
ans={2,3,1};
op(1);
}
else if(n==7){
ans=ans7;
op(1);
}
else{
op(0);
}
return;
}
ll lb;
for(int i=20;i>=0;i--){
if(n&(1<<i)){
lb=i;
break;
}
}
if(!(n&(1<<(lb-1)))){
op(0);
return;
}
if(n==(1<<lb)+(1<<(lb-1))){
op(0);
return;
}
for(int i=3;i<=lb;i++){
ans.push_back((1<<i)+(1<<(i-1)));
ans.push_back(1<<i);
}
fill(1<<lb,(1<<(lb-1))-1,1);
for(int i=(1<<lb)+(1<<(lb-1))+2;i<=n;i++){
follow[i-(1<<(lb-1))].push_back(i);
}
ans.push_back((1<<lb)+(1<<(lb-1))+1);
for(int b=lb-1;b>=3;b--){
fill((1<<b),1,(1<<b)-2);
// follow[(1<<b)].push_back((1<<b)+(1<<(b-1)));
}
for(int i=0;i<7;i++){
ans.push_back(ans7[i]);
}
op(1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3616kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
3
output:
YES 2 3 1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
7
output:
YES 7 5 4 6 2 3 1
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
13
output:
YES 12 8 10 11 9 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #14:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
14
output:
YES 12 8 10 14 11 9 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #15:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
15
output:
YES 12 8 10 14 11 15 9 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #16:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
16
output:
NO
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
17
output:
NO
result:
ok answer is 0
Test #18:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
23
output:
NO
result:
ok answer is 0
Test #19:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
24
output:
NO
result:
ok answer is 0
Test #20:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
25
output:
YES 12 8 24 16 20 21 23 22 18 19 17 25 9 11 10 14 15 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #21:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
26
output:
YES 12 8 24 16 20 21 23 22 18 26 19 17 25 9 11 10 14 15 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #22:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
27
output:
YES 12 8 24 16 20 21 23 22 18 26 19 27 17 25 9 11 10 14 15 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #23:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
40
output:
NO
result:
ok answer is 0
Test #24:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
53
output:
YES 12 8 24 16 48 32 40 41 43 42 46 47 45 44 36 52 37 53 39 38 34 50 35 51 33 49 17 19 18 22 23 21 20 28 29 31 30 26 27 25 9 11 10 14 15 13 7 5 4 6 2 3 1
result:
ok answer is 1
Test #25:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
93
output:
NO
result:
ok answer is 0
Test #26:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
105
output:
YES 12 8 24 16 48 32 96 64 80 81 83 82 86 87 85 84 92 93 95 94 90 91 89 88 72 104 73 105 75 74 78 79 77 76 68 100 69 101 71 103 70 102 66 98 67 99 65 97 33 35 34 38 39 37 36 44 45 47 46 42 43 41 40 56 57 59 58 62 63 61 60 52 53 55 54 50 51 49 17 19 18 22 23 21 20 28 29 31 30 26 27 25 9 11 10 14 15 1...
result:
ok answer is 1
Test #27:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
132
output:
NO
result:
ok answer is 0
Test #28:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
221
output:
YES 12 8 24 16 48 32 96 64 192 128 160 161 163 162 166 167 165 164 172 173 175 174 170 171 169 168 184 185 187 186 190 191 189 188 180 181 183 182 178 179 177 176 144 208 145 209 147 211 146 210 150 214 151 215 149 213 148 212 156 220 157 221 159 158 154 218 155 219 153 217 152 216 136 200 137 201 1...
result:
ok answer is 1
Test #29:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
373
output:
NO
result:
ok answer is 0
Test #30:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
473
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 320 448 321 449 323 451 322 450 326 454 327 455 325 453 324 452 332 460 333 461 335 463 334 462 330 458 331 459 329 457 328 456 344 472 345 473 347 346 350 351 349 348 340 468 341 469 343 471 342 470 338 466 339 467 337 465 336 464 368 369 371 370 374 375 3...
result:
ok answer is 1
Test #31:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
513
output:
NO
result:
ok answer is 0
Test #32:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
934
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 640 896 641 897 643 899 642 898 646 902 647 903 645 901 644 900 652 908 653 909 655 911 654 910 650 906 651 907 649 905 648 904 664 920 665 921 667 923 666 922 670 926 671 927 669 925 668 924 660 916 661 917 663 919 662 918 658 914 659 915 657 913 6...
result:
ok answer is 1
Test #33:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1356
output:
NO
result:
ok answer is 0
Test #34:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
1651
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 1280 1281 1283 1282 1286 1287 1285 1284 1292 1293 1295 1294 1290 1291 1289 1288 1304 1305 1307 1306 1310 1311 1309 1308 1300 1301 1303 1302 1298 1299 1297 1296 1328 1329 1331 1330 1334 1335 1333 1332 1340 1341 1343 1342 1338 1339 1337 1336...
result:
ok answer is 1
Test #35:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
2263
output:
NO
result:
ok answer is 0
Test #36:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
3330
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 2560 2561 2563 2562 2566 2567 2565 2564 2572 2573 2575 2574 2570 2571 2569 2568 2584 2585 2587 2586 2590 2591 2589 2588 2580 2581 2583 2582 2578 2579 2577 2576 2608 2609 2611 2610 2614 2615 2613 2612 2620 2621 2623 2622 2618 2619...
result:
ok answer is 1
Test #37:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
4375
output:
NO
result:
ok answer is 0
Test #38:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
7989
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 5120 7168 5121 7169 5123 7171 5122 7170 5126 7174 5127 7175 5125 7173 5124 7172 5132 7180 5133 7181 5135 7183 5134 7182 5130 7178 5131 7179 5129 7177 5128 7176 5144 7192 5145 7193 5147 7195 5146 7194 5150 7198 5151 7199...
result:
ok answer is 1
Test #39:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
10925
output:
NO
result:
ok answer is 0
Test #40:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
14097
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 10240 10241 10243 10242 10246 10247 10245 10244 10252 10253 10255 10254 10250 10251 10249 10248 10264 10265 10267 10266 10270 10271 10269 10268 10260 10261 10263 10262 10258 10259 10257 10256 10288 10289 1029...
result:
ok answer is 1
Test #41:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
16893
output:
NO
result:
ok answer is 0
Test #42:
score: 0
Accepted
time: 3ms
memory: 4060kb
input:
28913
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 24576 16384 20480 28672 20481 28673 20483 28675 20482 28674 20486 28678 20487 28679 20485 28677 20484 28676 20492 28684 20493 28685 20495 28687 20494 28686 20490 28682 20491 28683 20489 28681 20488 28680 2050...
result:
ok answer is 1
Test #43:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
40092
output:
NO
result:
ok answer is 0
Test #44:
score: 0
Accepted
time: 0ms
memory: 4148kb
input:
54980
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 24576 16384 49152 32768 40960 40961 40963 40962 40966 40967 40965 40964 40972 40973 40975 40974 40970 40971 40969 40968 40984 40985 40987 40986 40990 40991 40989 40988 40980 40981 40983 40982 40978 40979 4097...
result:
ok answer is 1
Test #45:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
88104
output:
NO
result:
ok answer is 0
Test #46:
score: 0
Accepted
time: 3ms
memory: 4724kb
input:
106284
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 24576 16384 49152 32768 98304 65536 81920 81921 81923 81922 81926 81927 81925 81924 81932 81933 81935 81934 81930 81931 81929 81928 81944 81945 81947 81946 81950 81951 81949 81948 81940 81941 81943 81942 8193...
result:
ok answer is 1
Test #47:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
152797
output:
NO
result:
ok answer is 0
Test #48:
score: 0
Accepted
time: 11ms
memory: 5672kb
input:
200000
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 24576 16384 49152 32768 98304 65536 196608 131072 163840 163841 163843 163842 163846 163847 163845 163844 163852 163853 163855 163854 163850 163851 163849 163848 163864 163865 163867 163866 163870 163871 1638...
result:
ok answer is 1
Test #49:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3073
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 2560 2561 2563 2562 2566 2567 2565 2564 2572 2573 2575 2574 2570 2571 2569 2568 2584 2585 2587 2586 2590 2591 2589 2588 2580 2581 2583 2582 2578 2579 2577 2576 2608 2609 2611 2610 2614 2615 2613 2612 2620 2621 2623 2622 2618 2619...
result:
ok answer is 1
Test #50:
score: 0
Accepted
time: 0ms
memory: 4232kb
input:
16383
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 10240 14336 10241 14337 10243 14339 10242 14338 10246 14342 10247 14343 10245 14341 10244 14340 10252 14348 10253 14349 10255 14351 10254 14350 10250 14346 10251 14347 10249 14345 10248 14344 10264 14360 1026...
result:
ok answer is 1
Test #51:
score: 0
Accepted
time: 3ms
memory: 4244kb
input:
32767
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 768 512 1536 1024 3072 2048 6144 4096 12288 8192 24576 16384 20480 28672 20481 28673 20483 28675 20482 28674 20486 28678 20487 28679 20485 28677 20484 28676 20492 28684 20493 28685 20495 28687 20494 28686 20490 28682 20491 28683 20489 28681 20488 28680 2050...
result:
ok answer is 1
Test #52:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
399
output:
YES 12 8 24 16 48 32 96 64 192 128 384 256 320 321 323 322 326 327 325 324 332 333 335 334 330 331 329 328 344 345 347 346 350 351 349 348 340 341 343 342 338 339 337 336 368 369 371 370 374 375 373 372 380 381 383 382 378 379 377 376 360 361 363 362 366 367 365 364 356 357 359 358 354 355 353 352 2...
result:
ok answer is 1
Test #53:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
5757
output:
NO
result:
ok answer is 0
Test #54:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
179
output:
NO
result:
ok answer is 0
Test #55:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
228
output:
YES 12 8 24 16 48 32 96 64 192 128 160 224 161 225 163 227 162 226 166 167 165 164 228 172 173 175 174 170 171 169 168 184 185 187 186 190 191 189 188 180 181 183 182 178 179 177 176 144 208 145 209 147 211 146 210 150 214 151 215 149 213 148 212 156 220 157 221 159 223 158 222 154 218 155 219 153 2...
result:
ok answer is 1
Extra Test:
score: 0
Extra Test Passed