QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #307470 | #8004. Bit Component | ucup_team_qiuly# | AC ✓ | 9ms | 4824kb | C++14 | 1.7kb | 2024-01-18 17:12:13 | 2024-01-18 17:12:14 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
_f = 0, x = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = - x;
}
signed main () {
int n; IN (n);
if (n == 1) return printf ("YES\n1\n"), 0;
if (n == 3) return printf ("YES\n2 3 1\n"), 0;
vector <int> ans (n + 1);
int m = 0; for ( ; (1 << m) <= n; ++ m);
auto bit = [&] (int x, int b) { return (x >> b) & 1; };
int p = 1 << m - 1;
int q = p + (1 << m - 2);
if (n < q + 1) return puts ("NO"), 0;
{ // [1, p - 1]
vector <int> s (1, 0);
lep (t, 1, m - 1) {
vector <int> _s;
lep (i, 0, (1 << t - 1) - 1) _s.emplace_back ( s[i] << 1 );
rep (i, (1 << t - 1) - 1, 0) _s.emplace_back ( (s[i] << 1) | 1);
swap (s, _s);
}
int u = (1 << m - 2) + 1;
lep (i, u + 1, p - 1) swap (s[i], s[u]);
lep (i, 1, p - 1) ans[i] = s[i];
}
int x = p;
{
vector <int> s (1, 0);
lep (t, 1, m - 2) {
vector <int> _s;
lep (i, 0, (1 << t - 1) - 1) _s.emplace_back ( s[i] );
rep (i, (1 << t - 1) - 1, 0) _s.emplace_back ( s[i] | (1 << t - 1) );
swap (s, _s);
}
lep (i, 1, q - p - 1) {
if ((s[i] | q) <= n) ans[x ++ ] = s[i] | q;
ans[x ++ ] = s[i] | p;
}
}
ans[x ++ ] = p, ans[x ++ ] = q;
puts ("YES");
lep (i, 1, n) printf ("%d%c", ans[i], " \n"[i == n]);
/* lep (i, 1, n) {
lep (j, 0, m - 1) debug ("%d", bit (ans[i], j));
debug ("\n");
} */
return 0;
}
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
1
output:
YES 1
result:
ok answer is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2
output:
NO
result:
ok answer is 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3
output:
YES 2 3 1
result:
ok answer is 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4
output:
NO
result:
ok answer is 0
Test #5:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
5
output:
NO
result:
ok answer is 0
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
6
output:
NO
result:
ok answer is 0
Test #7:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
7
output:
YES 2 3 1 7 5 4 6
result:
ok answer is 1
Test #8:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
8
output:
NO
result:
ok answer is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
9
output:
NO
result:
ok answer is 0
Test #10:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
10
output:
NO
result:
ok answer is 0
Test #11:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
11
output:
NO
result:
ok answer is 0
Test #12:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
12
output:
NO
result:
ok answer is 0
Test #13:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
13
output:
YES 4 6 2 3 1 7 5 13 9 11 10 8 12
result:
ok answer is 1
Test #14:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
14
output:
YES 4 6 2 3 1 7 5 13 9 11 14 10 8 12
result:
ok answer is 1
Test #15:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
15
output:
YES 4 6 2 3 1 7 5 13 9 15 11 14 10 8 12
result:
ok answer is 1
Test #16:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
16
output:
NO
result:
ok answer is 0
Test #17:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
17
output:
NO
result:
ok answer is 0
Test #18:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
23
output:
NO
result:
ok answer is 0
Test #19:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
24
output:
NO
result:
ok answer is 0
Test #20:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
25
output:
YES 8 12 4 6 14 10 2 3 1 11 15 7 5 13 9 25 17 19 18 22 23 21 20 16 24
result:
ok answer is 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
26
output:
YES 8 12 4 6 14 10 2 3 1 11 15 7 5 13 9 25 17 19 26 18 22 23 21 20 16 24
result:
ok answer is 1
Test #22:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
27
output:
YES 8 12 4 6 14 10 2 3 1 11 15 7 5 13 9 25 17 27 19 26 18 22 23 21 20 16 24
result:
ok answer is 1
Test #23:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
40
output:
NO
result:
ok answer is 0
Test #24:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
53
output:
YES 16 24 8 12 28 20 4 6 22 30 14 10 26 18 2 3 1 19 27 11 15 31 23 7 5 21 29 13 9 25 17 49 33 51 35 50 34 38 39 53 37 52 36 44 45 47 46 42 43 41 40 32 48
result:
ok answer is 1
Test #25:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
93
output:
NO
result:
ok answer is 0
Test #26:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
105
output:
YES 32 48 16 24 56 40 8 12 44 60 28 20 52 36 4 6 38 54 22 30 62 46 14 10 42 58 26 18 50 34 2 3 1 35 51 19 27 59 43 11 15 47 63 31 23 55 39 7 5 37 53 21 29 61 45 13 9 41 57 25 17 49 33 97 65 99 67 98 66 102 70 103 71 101 69 100 68 76 77 79 78 74 75 105 73 104 72 88 89 91 90 94 95 93 92 84 85 87 86 82...
result:
ok answer is 1
Test #27:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
132
output:
NO
result:
ok answer is 0
Test #28:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
221
output:
YES 64 96 32 48 112 80 16 24 88 120 56 40 104 72 8 12 76 108 44 60 124 92 28 20 84 116 52 36 100 68 4 6 70 102 38 54 118 86 22 30 94 126 62 46 110 78 14 10 74 106 42 58 122 90 26 18 82 114 50 34 98 66 2 3 1 67 99 35 51 115 83 19 27 91 123 59 43 107 75 11 15 79 111 47 63 127 95 31 23 87 119 55 39 103...
result:
ok answer is 1
Test #29:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
373
output:
NO
result:
ok answer is 0
Test #30:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
473
output:
YES 128 192 64 96 224 160 32 48 176 240 112 80 208 144 16 24 152 216 88 120 248 184 56 40 168 232 104 72 200 136 8 12 140 204 76 108 236 172 44 60 188 252 124 92 220 156 28 20 148 212 84 116 244 180 52 36 164 228 100 68 196 132 4 6 134 198 70 102 230 166 38 54 182 246 118 86 214 150 22 30 158 222 94...
result:
ok answer is 1
Test #31:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
513
output:
NO
result:
ok answer is 0
Test #32:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
934
output:
YES 256 384 128 192 448 320 64 96 352 480 224 160 416 288 32 48 304 432 176 240 496 368 112 80 336 464 208 144 400 272 16 24 280 408 152 216 472 344 88 120 376 504 248 184 440 312 56 40 296 424 168 232 488 360 104 72 328 456 200 136 392 264 8 12 268 396 140 204 460 332 76 108 364 492 236 172 428 300...
result:
ok answer is 1
Test #33:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1356
output:
NO
result:
ok answer is 0
Test #34:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1651
output:
YES 512 768 256 384 896 640 128 192 704 960 448 320 832 576 64 96 608 864 352 480 992 736 224 160 672 928 416 288 800 544 32 48 560 816 304 432 944 688 176 240 752 1008 496 368 880 624 112 80 592 848 336 464 976 720 208 144 656 912 400 272 784 528 16 24 536 792 280 408 920 664 152 216 728 984 472 34...
result:
ok answer is 1
Test #35:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2263
output:
NO
result:
ok answer is 0
Test #36:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
3330
output:
YES 1024 1536 512 768 1792 1280 256 384 1408 1920 896 640 1664 1152 128 192 1216 1728 704 960 1984 1472 448 320 1344 1856 832 576 1600 1088 64 96 1120 1632 608 864 1888 1376 352 480 1504 2016 992 736 1760 1248 224 160 1184 1696 672 928 1952 1440 416 288 1312 1824 800 544 1568 1056 32 48 1072 1584 56...
result:
ok answer is 1
Test #37:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4375
output:
NO
result:
ok answer is 0
Test #38:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
7989
output:
YES 2048 3072 1024 1536 3584 2560 512 768 2816 3840 1792 1280 3328 2304 256 384 2432 3456 1408 1920 3968 2944 896 640 2688 3712 1664 1152 3200 2176 128 192 2240 3264 1216 1728 3776 2752 704 960 3008 4032 1984 1472 3520 2496 448 320 2368 3392 1344 1856 3904 2880 832 576 2624 3648 1600 1088 3136 2112 ...
result:
ok answer is 1
Test #39:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10925
output:
NO
result:
ok answer is 0
Test #40:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
14097
output:
YES 4096 6144 2048 3072 7168 5120 1024 1536 5632 7680 3584 2560 6656 4608 512 768 4864 6912 2816 3840 7936 5888 1792 1280 5376 7424 3328 2304 6400 4352 256 384 4480 6528 2432 3456 7552 5504 1408 1920 6016 8064 3968 2944 7040 4992 896 640 4736 6784 2688 3712 7808 5760 1664 1152 5248 7296 3200 2176 62...
result:
ok answer is 1
Test #41:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
16893
output:
NO
result:
ok answer is 0
Test #42:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
28913
output:
YES 8192 12288 4096 6144 14336 10240 2048 3072 11264 15360 7168 5120 13312 9216 1024 1536 9728 13824 5632 7680 15872 11776 3584 2560 10752 14848 6656 4608 12800 8704 512 768 8960 13056 4864 6912 15104 11008 2816 3840 12032 16128 7936 5888 14080 9984 1792 1280 9472 13568 5376 7424 15616 11520 3328 23...
result:
ok answer is 1
Test #43:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
40092
output:
NO
result:
ok answer is 0
Test #44:
score: 0
Accepted
time: 4ms
memory: 3844kb
input:
54980
output:
YES 16384 24576 8192 12288 28672 20480 4096 6144 22528 30720 14336 10240 26624 18432 2048 3072 19456 27648 11264 15360 31744 23552 7168 5120 21504 29696 13312 9216 25600 17408 1024 1536 17920 26112 9728 13824 30208 22016 5632 7680 24064 32256 15872 11776 28160 19968 3584 2560 18944 27136 10752 14848...
result:
ok answer is 1
Test #45:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
88104
output:
NO
result:
ok answer is 0
Test #46:
score: 0
Accepted
time: 7ms
memory: 4180kb
input:
106284
output:
YES 32768 49152 16384 24576 57344 40960 8192 12288 45056 61440 28672 20480 53248 36864 4096 6144 38912 55296 22528 30720 63488 47104 14336 10240 43008 59392 26624 18432 51200 34816 2048 3072 35840 52224 19456 27648 60416 44032 11264 15360 48128 64512 31744 23552 56320 39936 7168 5120 37888 54272 215...
result:
ok answer is 1
Test #47:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
152797
output:
NO
result:
ok answer is 0
Test #48:
score: 0
Accepted
time: 9ms
memory: 4824kb
input:
200000
output:
YES 65536 98304 32768 49152 114688 81920 16384 24576 90112 122880 57344 40960 106496 73728 8192 12288 77824 110592 45056 61440 126976 94208 28672 20480 86016 118784 53248 36864 102400 69632 4096 6144 71680 104448 38912 55296 120832 88064 22528 30720 96256 129024 63488 47104 112640 79872 14336 10240 ...
result:
ok answer is 1
Test #49:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
3073
output:
YES 1024 1536 512 768 1792 1280 256 384 1408 1920 896 640 1664 1152 128 192 1216 1728 704 960 1984 1472 448 320 1344 1856 832 576 1600 1088 64 96 1120 1632 608 864 1888 1376 352 480 1504 2016 992 736 1760 1248 224 160 1184 1696 672 928 1952 1440 416 288 1312 1824 800 544 1568 1056 32 48 1072 1584 56...
result:
ok answer is 1
Test #50:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
16383
output:
YES 4096 6144 2048 3072 7168 5120 1024 1536 5632 7680 3584 2560 6656 4608 512 768 4864 6912 2816 3840 7936 5888 1792 1280 5376 7424 3328 2304 6400 4352 256 384 4480 6528 2432 3456 7552 5504 1408 1920 6016 8064 3968 2944 7040 4992 896 640 4736 6784 2688 3712 7808 5760 1664 1152 5248 7296 3200 2176 62...
result:
ok answer is 1
Test #51:
score: 0
Accepted
time: 2ms
memory: 3888kb
input:
32767
output:
YES 8192 12288 4096 6144 14336 10240 2048 3072 11264 15360 7168 5120 13312 9216 1024 1536 9728 13824 5632 7680 15872 11776 3584 2560 10752 14848 6656 4608 12800 8704 512 768 8960 13056 4864 6912 15104 11008 2816 3840 12032 16128 7936 5888 14080 9984 1792 1280 9472 13568 5376 7424 15616 11520 3328 23...
result:
ok answer is 1
Test #52:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
399
output:
YES 128 192 64 96 224 160 32 48 176 240 112 80 208 144 16 24 152 216 88 120 248 184 56 40 168 232 104 72 200 136 8 12 140 204 76 108 236 172 44 60 188 252 124 92 220 156 28 20 148 212 84 116 244 180 52 36 164 228 100 68 196 132 4 6 134 198 70 102 230 166 38 54 182 246 118 86 214 150 22 30 158 222 94...
result:
ok answer is 1
Test #53:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
5757
output:
NO
result:
ok answer is 0
Test #54:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
179
output:
NO
result:
ok answer is 0
Test #55:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
228
output:
YES 64 96 32 48 112 80 16 24 88 120 56 40 104 72 8 12 76 108 44 60 124 92 28 20 84 116 52 36 100 68 4 6 70 102 38 54 118 86 22 30 94 126 62 46 110 78 14 10 74 106 42 58 122 90 26 18 82 114 50 34 98 66 2 3 1 67 99 35 51 115 83 19 27 91 123 59 43 107 75 11 15 79 111 47 63 127 95 31 23 87 119 55 39 103...
result:
ok answer is 1
Extra Test:
score: 0
Extra Test Passed