QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304636#8004. Bit Componentucup-team159#AC ✓13ms4176kbC++231.5kb2024-01-13 22:20:022024-01-13 22:20:02

Judging History

你现在查看的是最新测评结果

  • [2024-01-13 22:20:02]
  • 评测
  • 测评结果:AC
  • 用时:13ms
  • 内存:4176kb
  • [2024-01-13 22:20:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;

int gray(int x) {
    return x ^ (x >> 1);
}

int bitrev(int x, int k) {
    int y = 0;
    rep(i, k) {
        if (x >> i & 1) {
            y |= 1 << (k - 1 - i);
        }
    }
    return y;
}

vector<int> solve(int n) {
    if (n == 1) {
        return {1};
    }
    if (n == 3) {
        return {2, 3, 1};
    }
    rep(k, 20) {
        if (3 * (1 << k) + 1 <= n && n < 4 * (1 << k)) {
            vector<int> v;
            for (int x = 1; x <= 2 * (1 << k) - 2; x++) {
                v.pb(gray(x));
            }
            v.pb(3 * (1 << k) + 1);
            for (int x = (1 << k) - 1; x >= 0; x--) {
                v.pb(2 * (1 << k) + bitrev(gray(x), k));
                int y = 3 * (1 << k) + bitrev(gray(x), k);
                if (y <= n) {
                    if (y <= n && y != 3 * (1 << k) && y != 3 * (1 << k) + 1) {
                        v.pb(y);
                    }
                }
            }
            v.pb(3 * (1 << k));
            v.pb(1 << k);
            return v;
        }
    }
    return {};
}

int main() {
    int n;
    cin >> n;
    auto v = solve(n);
    if (v.empty()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        rep(i, n) {
            cout << v[i] << (i + 1 < n ? ' ' : '\n');
        }
    }
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3424kb

input:

1

output:

YES
1

result:

ok answer is 1

Test #2:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

2

output:

NO

result:

ok answer is 0

Test #3:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

3

output:

YES
2 3 1

result:

ok answer is 1

Test #4:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

4

output:

NO

result:

ok answer is 0

Test #5:

score: 0
Accepted
time: 0ms
memory: 3352kb

input:

5

output:

NO

result:

ok answer is 0

Test #6:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

6

output:

NO

result:

ok answer is 0

Test #7:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

7

output:

YES
1 3 7 5 4 6 2

result:

ok answer is 1

Test #8:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

8

output:

NO

result:

ok answer is 0

Test #9:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

9

output:

NO

result:

ok answer is 0

Test #10:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

10

output:

NO

result:

ok answer is 0

Test #11:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

11

output:

NO

result:

ok answer is 0

Test #12:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

12

output:

NO

result:

ok answer is 0

Test #13:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

13

output:

YES
1 3 2 6 7 5 13 9 11 10 8 12 4

result:

ok answer is 1

Test #14:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

14

output:

YES
1 3 2 6 7 5 13 9 11 10 14 8 12 4

result:

ok answer is 1

Test #15:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

15

output:

YES
1 3 2 6 7 5 13 9 11 15 10 14 8 12 4

result:

ok answer is 1

Test #16:

score: 0
Accepted
time: 0ms
memory: 3412kb

input:

16

output:

NO

result:

ok answer is 0

Test #17:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

17

output:

NO

result:

ok answer is 0

Test #18:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

23

output:

NO

result:

ok answer is 0

Test #19:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

24

output:

NO

result:

ok answer is 0

Test #20:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

25

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 25 17 21 23 19 18 22 20 16 24 8

result:

ok answer is 1

Test #21:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

26

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 25 17 21 23 19 18 26 22 20 16 24 8

result:

ok answer is 1

Test #22:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

27

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 25 17 21 23 19 27 18 26 22 20 16 24 8

result:

ok answer is 1

Test #23:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

40

output:

NO

result:

ok answer is 0

Test #24:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

53

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 49 33 41 45 37 53 39 47 43 35 51 34 50 42 46 38 36 52 44 40 32 48 16

result:

ok answer is 1

Test #25:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

93

output:

NO

result:

ok answer is 0

Test #26:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

105

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 97 65 81 89 73 105 77 93 85 69 101 71 103 87 95 79 75 91 83 67 99 66 98 82 90 74 78 94 86 70 102 68 100 84 92 76 72 104...

result:

ok answer is 1

Test #27:

score: 0
Accepted
time: 0ms
memory: 3416kb

input:

132

output:

NO

result:

ok answer is 0

Test #28:

score: 0
Accepted
time: 0ms
memory: 3416kb

input:

221

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #29:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

373

output:

NO

result:

ok answer is 0

Test #30:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

473

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #31:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

513

output:

NO

result:

ok answer is 0

Test #32:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

934

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #33:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

1356

output:

NO

result:

ok answer is 0

Test #34:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

1651

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #35:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

2263

output:

NO

result:

ok answer is 0

Test #36:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

3330

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #37:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

4375

output:

NO

result:

ok answer is 0

Test #38:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

7989

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #39:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

10925

output:

NO

result:

ok answer is 0

Test #40:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

14097

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #41:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

16893

output:

NO

result:

ok answer is 0

Test #42:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

28913

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #43:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

40092

output:

NO

result:

ok answer is 0

Test #44:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

54980

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #45:

score: 0
Accepted
time: 1ms
memory: 3420kb

input:

88104

output:

NO

result:

ok answer is 0

Test #46:

score: 0
Accepted
time: 8ms
memory: 3836kb

input:

106284

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #47:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

152797

output:

NO

result:

ok answer is 0

Test #48:

score: 0
Accepted
time: 13ms
memory: 4176kb

input:

200000

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #49:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

3073

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #50:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

16383

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #51:

score: 0
Accepted
time: 3ms
memory: 3540kb

input:

32767

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #52:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

399

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Test #53:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

5757

output:

NO

result:

ok answer is 0

Test #54:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

179

output:

NO

result:

ok answer is 0

Test #55:

score: 0
Accepted
time: 0ms
memory: 3420kb

input:

228

output:

YES
1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 ...

result:

ok answer is 1

Extra Test:

score: 0
Extra Test Passed