QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #438529 | #8004. Bit Component | real_sigma_team# | AC ✓ | 72ms | 8300kb | C++23 | 1.6kb | 2024-06-10 19:11:38 | 2024-06-10 19:11:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int rev(int x, int k) {
vector<int> bit;
for (int i = 0; i < k; ++i)
bit.push_back(bool((1 << i) & x));
reverse(bit.begin(), bit.end());
int y = 0;
for (int i = 0; i < k; ++i)
if (bit[i])
y += (1 << i);
return y;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
if (n == 1) {
cout << "YES\n1";
return 0;
}
if (n == 3) {
cout << "YES\n2 3 1";
return 0;
}
int k = __lg(n);
if (n <= (1 << k) + (1 << (k - 1))) {
cout << "NO";
return 0;
}
cout << "YES\n";
if (n == 7) {
cout << "7 5 1 3 2 6 4";
return 0;
}
vector<vector<int>> solve(k + 2);
solve[2] = {1, 3, 2};
solve[3] = {7, 5, 1, 3, 2, 6, 4};
for (int i = 4; i <= k + 1; ++i) {
solve[i].push_back((1 << i) - 1);
for (int j: solve[i - 2]) {
solve[i].push_back(rev(j, i - 2) + (1 << (i - 1)));
if (rev(j, i - 2) != 1 && rev(j, i - 2) + (1 << (i - 1)) + (1 << (i - 2)) != (1 << i) - 1)
solve[i].push_back(rev(j, i - 2) + (1 << (i - 1)) + (1 << (i - 2)));
}
solve[i].push_back((1 << (i - 1)) + (1 << (i - 2)) + 1);
for (int j: solve[i - 1])
solve[i].push_back(j);
solve[i].push_back((1 << (i - 1)) + (1 << (i - 2)));
solve[i].push_back((1 << (i - 1)));
}
for (int i: solve[k + 1])
if (i <= n)
cout << i << ' ';
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
3
output:
YES 2 3 1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
7
output:
YES 7 5 1 3 2 6 4
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
13
output:
YES 10 11 9 13 7 5 1 3 2 6 4 12 8
result:
ok answer is 1
Test #14:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
14
output:
YES 10 14 11 9 13 7 5 1 3 2 6 4 12 8
result:
ok answer is 1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
15
output:
YES 15 10 14 11 9 13 7 5 1 3 2 6 4 12 8
result:
ok answer is 1
Test #16:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
16
output:
NO
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
17
output:
NO
result:
ok answer is 0
Test #18:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
23
output:
NO
result:
ok answer is 0
Test #19:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
24
output:
NO
result:
ok answer is 0
Test #20:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
25
output:
YES 23 21 20 22 18 19 17 25 15 10 14 11 9 13 7 5 1 3 2 6 4 12 8 24 16
result:
ok answer is 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
26
output:
YES 23 21 20 22 18 26 19 17 25 15 10 14 11 9 13 7 5 1 3 2 6 4 12 8 24 16
result:
ok answer is 1
Test #22:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
27
output:
YES 23 21 20 22 18 26 19 27 17 25 15 10 14 11 9 13 7 5 1 3 2 6 4 12 8 24 16
result:
ok answer is 1
Test #23:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
40
output:
NO
result:
ok answer is 0
Test #24:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
53
output:
YES 47 37 53 39 45 41 43 46 42 40 44 36 52 38 34 50 35 51 33 49 31 23 21 29 20 28 22 30 18 26 19 27 17 25 15 10 14 11 9 13 7 5 1 3 2 6 4 12 8 24 16 48 32
result:
ok answer is 1
Test #25:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
93
output:
NO
result:
ok answer is 0
Test #26:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
105
output:
YES 95 93 85 87 69 101 71 103 77 79 73 105 75 89 91 81 83 94 74 78 90 82 86 92 84 80 88 72 104 76 68 100 70 102 66 98 67 99 65 97 63 47 37 53 39 55 45 61 41 57 43 59 46 62 42 58 40 56 44 60 36 52 38 54 34 50 35 51 33 49 31 23 21 29 20 28 22 30 18 26 19 27 17 25 15 10 14 11 9 13 7 5 1 3 2 6 4 12 8 24...
result:
ok answer is 1
Test #27:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
132
output:
NO
result:
ok answer is 0
Test #28:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
221
output:
YES 191 189 169 171 185 187 173 175 165 167 181 183 157 221 159 149 213 151 215 133 197 135 199 141 205 143 207 137 201 139 203 153 217 155 219 145 209 147 211 177 179 161 163 190 186 170 174 138 202 142 206 154 218 158 146 210 150 214 178 182 162 166 188 148 212 156 220 180 164 172 184 168 160 176 ...
result:
ok answer is 1
Test #29:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
373
output:
NO
result:
ok answer is 0
Test #30:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
473
output:
YES 383 381 349 351 341 469 343 471 373 375 337 465 339 467 369 371 345 473 347 377 379 329 457 331 459 361 363 333 461 335 463 365 367 325 453 327 455 357 359 317 445 319 447 297 425 299 427 313 441 315 443 301 429 303 431 293 421 295 423 309 437 311 439 285 413 287 415 277 405 279 407 261 389 263 ...
result:
ok answer is 1
Test #31:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
513
output:
NO
result:
ok answer is 0
Test #32:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
934
output:
YES 767 765 701 703 661 917 663 919 725 727 669 925 671 927 733 735 693 695 757 759 677 933 679 741 743 685 687 749 751 697 699 761 763 681 683 745 747 673 929 675 931 737 739 689 691 753 755 657 913 659 915 721 723 665 921 667 923 729 731 649 905 651 907 713 715 653 909 655 911 717 719 645 901 647 ...
result:
ok answer is 1
Test #33:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
1356
output:
NO
result:
ok answer is 0
Test #34:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
1651
output:
YES 1535 1533 1405 1407 1397 1399 1525 1527 1365 1367 1493 1495 1373 1375 1501 1503 1301 1303 1429 1431 1309 1311 1437 1439 1333 1335 1461 1463 1341 1343 1469 1471 1317 1319 1445 1447 1325 1327 1453 1455 1381 1383 1509 1511 1389 1391 1517 1519 1349 1351 1477 1479 1357 1359 1485 1487 1401 1403 1529 1...
result:
ok answer is 1
Test #35:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
2263
output:
NO
result:
ok answer is 0
Test #36:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
3330
output:
YES 3071 3069 2813 2815 2805 2807 3061 3063 2725 2727 2981 2983 2733 2735 2989 2991 2789 2791 3045 3047 2797 2799 3053 3055 2741 2743 2997 2999 2749 2751 3005 3007 2709 2711 2965 2967 2717 2719 2973 2975 2773 2775 3029 3031 2781 2783 3037 3039 2677 2679 2933 2935 2685 2687 2941 2943 2645 2647 2901 2...
result:
ok answer is 1
Test #37:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
4375
output:
NO
result:
ok answer is 0
Test #38:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
7989
output:
YES 6143 6141 5629 7677 5631 7679 5621 7669 5623 7671 6133 6135 5493 7541 5495 7543 6005 6007 5501 7549 5503 7551 6013 6015 5461 7509 5463 7511 5973 5975 5469 7517 5471 7519 5981 5983 5589 7637 5591 7639 6101 6103 5597 7645 5599 7647 6109 6111 5445 7493 5447 7495 5957 5959 5453 7501 5455 7503 5965 5...
result:
ok answer is 1
Test #39:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
10925
output:
NO
result:
ok answer is 0
Test #40:
score: 0
Accepted
time: 5ms
memory: 3684kb
input:
14097
output:
YES 12287 12285 11261 11263 11253 11255 12277 12279 10997 10999 12021 12023 11005 11007 12029 12031 10837 10839 11861 11863 10845 10847 11869 11871 11093 11095 12117 12119 11101 11103 12125 12127 10869 10871 11893 11895 10877 10879 11901 11903 11125 11127 12149 12151 11133 11135 12157 12159 10965 10...
result:
ok answer is 1
Test #41:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
16893
output:
NO
result:
ok answer is 0
Test #42:
score: 0
Accepted
time: 10ms
memory: 3964kb
input:
28913
output:
YES 24575 24573 22525 22527 22517 22519 24565 24567 22005 22007 24053 24055 22013 22015 24061 24063 21973 21975 24021 24023 21981 21983 24029 24031 22485 22487 24533 24535 22493 22495 24541 24543 21845 21847 23893 23895 21853 21855 23901 23903 22357 22359 24405 24407 22365 22367 24413 24415 21877 21...
result:
ok answer is 1
Test #43:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
40092
output:
NO
result:
ok answer is 0
Test #44:
score: 0
Accepted
time: 20ms
memory: 4376kb
input:
54980
output:
YES 49151 49149 45053 45055 45045 45047 49141 49143 44021 44023 48117 48119 44029 44031 48125 48127 43989 43991 48085 48087 43997 43999 48093 48095 45013 45015 49109 49111 45021 45023 49117 49119 43669 43671 47765 47767 43677 43679 47773 47775 44693 44695 48789 48791 44701 44703 48797 48799 43701 43...
result:
ok answer is 1
Test #45:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
88104
output:
NO
result:
ok answer is 0
Test #46:
score: 0
Accepted
time: 34ms
memory: 5820kb
input:
106284
output:
YES 98303 98301 90109 90111 90101 90103 98293 98295 88053 88055 96245 96247 88061 88063 96253 96255 88021 88023 96213 96215 88029 88031 96221 96223 90069 90071 98261 98263 90077 90079 98269 98271 87509 87511 95701 95703 87517 87519 95709 95711 89557 89559 97749 97751 89565 89567 97757 97759 87541 87...
result:
ok answer is 1
Test #47:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
152797
output:
NO
result:
ok answer is 0
Test #48:
score: 0
Accepted
time: 72ms
memory: 8300kb
input:
200000
output:
YES 196607 196605 180221 180223 180213 180215 196597 196599 176117 176119 192501 192503 176125 176127 192509 192511 176085 176087 192469 192471 176093 176095 192477 192479 180181 180183 196565 196567 180189 180191 196573 196575 175061 175063 191445 191447 175069 175071 191453 191455 179157 179159 19...
result:
ok answer is 1
Test #49:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3073
output:
YES 3071 3069 2813 2815 2805 2807 3061 3063 2725 2727 2981 2983 2733 2735 2989 2991 2789 2791 3045 3047 2797 2799 3053 3055 2741 2743 2997 2999 2749 2751 3005 3007 2709 2711 2965 2967 2717 2719 2973 2975 2773 2775 3029 3031 2781 2783 3037 3039 2677 2679 2933 2935 2685 2687 2941 2943 2645 2647 2901 2...
result:
ok answer is 1
Test #50:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
16383
output:
YES 16383 12287 12285 16381 11261 15357 11263 15359 11253 15349 11255 15351 12277 16373 12279 16375 10997 15093 10999 15095 12021 16117 12023 16119 11005 15101 11007 15103 12029 16125 12031 16127 10837 14933 10839 14935 11861 15957 11863 15959 10845 14941 10847 14943 11869 15965 11871 15967 11093 15...
result:
ok answer is 1
Test #51:
score: 0
Accepted
time: 10ms
memory: 3968kb
input:
32767
output:
YES 32767 24575 24573 32765 22525 30717 22527 30719 22517 30709 22519 30711 24565 32757 24567 32759 22005 30197 22007 30199 24053 32245 24055 32247 22013 30205 22015 30207 24061 32253 24063 32255 21973 30165 21975 30167 24021 32213 24023 32215 21981 30173 21983 30175 24029 32221 24031 32223 22485 30...
result:
ok answer is 1
Test #52:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
399
output:
YES 383 381 349 351 341 343 373 375 337 339 369 371 345 347 377 379 329 331 361 363 333 335 365 367 325 327 357 359 317 319 297 299 313 315 301 303 293 295 309 311 285 287 277 279 261 389 263 391 269 397 271 399 265 393 267 395 281 283 273 275 305 307 289 291 353 355 321 323 382 378 338 342 370 374 ...
result:
ok answer is 1
Test #53:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
5757
output:
NO
result:
ok answer is 0
Test #54:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
179
output:
NO
result:
ok answer is 0
Test #55:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
228
output:
YES 191 189 169 171 185 187 173 175 165 167 181 183 157 221 159 223 149 213 151 215 133 197 135 199 141 205 143 207 137 201 139 203 153 217 155 219 145 209 147 211 177 179 161 225 163 227 190 186 170 174 138 202 142 206 154 218 158 222 146 210 150 214 178 182 162 226 166 188 148 212 156 220 180 164 ...
result:
ok answer is 1
Extra Test:
score: 0
Extra Test Passed