QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305965#8004. Bit ComponentckisekiAC ✓6ms5748kbC++201.8kb2024-01-16 06:37:352024-01-16 06:37:35

Judging History

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

  • [2024-01-16 06:37:35]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:5748kb
  • [2024-01-16 06:37:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

vector<int> f(int n) {
    // cerr << "n = " << n << endl;

    if (n == 7) {
        return {1, 3, 2, 6, 4, 5, 7};
    }

    if (n == 15) {
        return {1, 3, 2, 6, 4, 5, 7, 13, 9, 11, 10, 8, 12, 14, 15};
    }

    int k = 1;
    while (k*2 <= n) k *= 2;

    //  cerr << "k = " << k << endl;
    if (n <= k / 2 * 3) {
        return {};
    }
    auto A = f(k - 1);
    auto B = f(k/2 - 1);

    vector<int> res = A;
    int U = k*2 - 1;
    for (int x: B) {
        int u = x | k;
        int v = u | (k/2);
        // cerr << "u = " << u << ' ' << bitset<5>(u) << endl;
        // cerr << "v = " << v << ' ' << bitset<5>(v) << endl;
        if (v != U && v <= n) res.push_back(v);
        if (u != k + 1) res.push_back(u);
    }
    res.push_back(k + 1);
    res.push_back(k);
    if ((k | (k/2)) <= n) res.push_back(k | (k/2));
    if (U <= n) res.push_back(U);
    return res;
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);

    int n;
    cin >> n;
    if (n == 1) {
        cout << "YES\n1\n";
        return 0;
    }

    if (n == 3) {
        cout << "YES\n2 3 1\n";
        return 0;
    }

    auto res = f(n);
    if (n == 13 || n == 14) {
        res = f(15);
        res.resize(n);
    }
    if (res.empty()) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    for (int x: res) {
        cout << x << ' ';
        /* cout << x << '\t';
        for (int i = 0; i < 20; i++)
           cout << " #"[(x >> i & 1)];
        cout << endl; */
    }
    /* set<int> st(res.begin(), res.end());
    for (int i = 1; i <= n; i++)
        if (!st.count(i))
            cerr << "i = " << i << endl;
    cerr << res.size() << endl; */
    cout << '\n';
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

1

output:

YES
1

result:

ok answer is 1

Test #2:

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

input:

2

output:

NO

result:

ok answer is 0

Test #3:

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

input:

3

output:

YES
2 3 1

result:

ok answer is 1

Test #4:

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

input:

4

output:

NO

result:

ok answer is 0

Test #5:

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

input:

5

output:

NO

result:

ok answer is 0

Test #6:

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

input:

6

output:

NO

result:

ok answer is 0

Test #7:

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

input:

7

output:

YES
1 3 2 6 4 5 7 

result:

ok answer is 1

Test #8:

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

input:

8

output:

NO

result:

ok answer is 0

Test #9:

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

input:

9

output:

NO

result:

ok answer is 0

Test #10:

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

input:

10

output:

NO

result:

ok answer is 0

Test #11:

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

input:

11

output:

NO

result:

ok answer is 0

Test #12:

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

input:

12

output:

NO

result:

ok answer is 0

Test #13:

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

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: 0ms
memory: 3632kb

input:

14

output:

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

result:

ok answer is 1

Test #15:

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

input:

15

output:

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

result:

ok answer is 1

Test #16:

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

input:

16

output:

NO

result:

ok answer is 0

Test #17:

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

input:

17

output:

NO

result:

ok answer is 0

Test #18:

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

input:

23

output:

NO

result:

ok answer is 0

Test #19:

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

input:

24

output:

NO

result:

ok answer is 0

Test #20:

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

input:

25

output:

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

result:

ok answer is 1

Test #21:

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

input:

26

output:

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

result:

ok answer is 1

Test #22:

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

input:

27

output:

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

result:

ok answer is 1

Test #23:

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

input:

40

output:

NO

result:

ok answer is 0

Test #24:

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

input:

53

output:

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

result:

ok answer is 1

Test #25:

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

input:

93

output:

NO

result:

ok answer is 0

Test #26:

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

input:

105

output:

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

result:

ok answer is 1

Test #27:

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

input:

132

output:

NO

result:

ok answer is 0

Test #28:

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

input:

221

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #29:

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

input:

373

output:

NO

result:

ok answer is 0

Test #30:

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

input:

473

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #31:

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

input:

513

output:

NO

result:

ok answer is 0

Test #32:

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

input:

934

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #33:

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

input:

1356

output:

NO

result:

ok answer is 0

Test #34:

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

input:

1651

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #35:

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

input:

2263

output:

NO

result:

ok answer is 0

Test #36:

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

input:

3330

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #37:

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

input:

4375

output:

NO

result:

ok answer is 0

Test #38:

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

input:

7989

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #39:

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

input:

10925

output:

NO

result:

ok answer is 0

Test #40:

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

input:

14097

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #41:

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

input:

16893

output:

NO

result:

ok answer is 0

Test #42:

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

input:

28913

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #43:

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

input:

40092

output:

NO

result:

ok answer is 0

Test #44:

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

input:

54980

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #45:

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

input:

88104

output:

NO

result:

ok answer is 0

Test #46:

score: 0
Accepted
time: 5ms
memory: 4356kb

input:

106284

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #47:

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

input:

152797

output:

NO

result:

ok answer is 0

Test #48:

score: 0
Accepted
time: 6ms
memory: 5748kb

input:

200000

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #49:

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

input:

3073

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #50:

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

input:

16383

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #51:

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

input:

32767

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #52:

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

input:

399

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Test #53:

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

input:

5757

output:

NO

result:

ok answer is 0

Test #54:

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

input:

179

output:

NO

result:

ok answer is 0

Test #55:

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

input:

228

output:

YES
1 3 2 6 4 5 7 13 9 11 10 8 12 14 15 25 27 19 26 18 30 22 28 20 29 21 23 17 16 24 31 49 51 35 50 34 54 38 52 36 53 37 55 39 61 45 57 41 59 43 58 42 56 40 60 44 62 46 47 33 32 48 63 97 99 67 98 66 102 70 100 68 101 69 103 71 109 77 105 73 107 75 106 74 104 72 108 76 110 78 111 79 121 89 123 91 115...

result:

ok answer is 1

Extra Test:

score: 0
Extra Test Passed