QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#630595#8174. Set Constructionucup-team3519#TL 1ms3692kbC++172.3kb2024-10-11 19:25:412024-10-11 19:25:42

Judging History

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

  • [2024-10-11 19:25:42]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3692kb
  • [2024-10-11 19:25:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
#define all1(x) (x).begin() + 1, (x).end()

typedef long long LL;

mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());

// void solve(int n, int aim) {
void solve() {
    // cout << "aim : " << aim << endl;
    // int n; cin >> n;
    // LL val = 1LL << n;
    // int n = mrand() % 59 + 2, aim = mrand() % (n * (n + 1) / 2 - 1) + 2;
    // cout << n << " " << aim << endl;
    int n, aim; cin >> n >> aim;

    auto check_good = [&](V<LL> hav) -> bool {
        set<LL> st;
        for(auto x : hav) st.insert(x);
        bool ok = 1;
        for(auto x : hav) {
            for(auto y : hav) {
                if(st.count(x & y) == 0) ok = 0;
                if(st.count(x | y) == 0) ok = 0;
                if(ok == 0) break;
            }
        }
        assert(st.count(0));
        assert(st.count((1LL << n) - 1));
        return ok;
    };

    // int aim = n * (n + 1) / 2;
    
    // n - __log(aim)



    int now = __lg(aim);
    if(aim == 1LL << now) now--;

    int base = now;
    LL part_bef = 0;
    int to_add = base;

    V<LL> ans;

    while(aim) {
        // cout << aim << " " << now << endl;
        if(aim == 1LL << now) {
            while(to_add < n) {
                part_bef += 1LL << to_add;
                to_add++;
            }
        }

        LL cur_part_bef_shuffle = part_bef;
        for(int i = base - 1, cnt = 1; cnt <= base - now; cnt++, i--) {
            cur_part_bef_shuffle += 1LL << i;
            // cout << "fuck" << endl;
        }

        for(int i = 0; i < (1 << now); i++) {
            // cout << aim << endl;
            ans.pb(cur_part_bef_shuffle + i);
            // cout << "fuck1" << endl;
        }

        aim -= 1LL << now;
        now = __lg(aim);
        part_bef += 1LL << to_add;
        to_add++;
    }

    assert(check_good(ans));
    // cout << "OK" << endl;
    for(auto x : ans) cout << x << ' ', assert(x >= 0);
    cout << endl;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    // for(int aim = 1; aim <= (1 << 4))
    // solve(5, 15);
    // for(int n = 2; n <= 60; n++) {
    //     for(int i = 2; i <= (n + 1) * (n) / 2; i++) solve(n , i);
    // }
    int t; cin >> t;
    while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
3 5
4 8
60 2

output:

0 1 2 3 7 
0 1 2 3 12 13 14 15 
0 1152921504606846975 

result:

ok AC

Test #2:

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

input:

30
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
6 21
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
7 11

output:

0 63 
0 1 63 
0 1 62 63 
0 1 2 3 63 
0 1 2 3 62 63 
0 1 2 3 6 7 63 
0 1 2 3 60 61 62 63 
0 1 2 3 4 5 6 7 63 
0 1 2 3 4 5 6 7 62 63 
0 1 2 3 4 5 6 7 14 15 63 
0 1 2 3 4 5 6 7 60 61 62 63 
0 1 2 3 4 5 6 7 12 13 14 15 63 
0 1 2 3 4 5 6 7 12 13 14 15 62 63 
0 1 2 3 4 5 6 7 12 13 14 15 30 31 63 
0 1 2 3 ...

result:

ok AC

Test #3:

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

input:

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

output:

0 1 2 3 4 5 6 7 124 125 126 127 
0 1 2 3 4 5 6 7 12 13 14 15 127 
0 1 2 3 4 5 6 7 12 13 14 15 126 127 
0 1 2 3 4 5 6 7 12 13 14 15 30 31 127 
0 1 2 3 4 5 6 7 120 121 122 123 124 125 126 127 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 127 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 126 127 
0 1 2 3 4 5 6 7 8 9...

result:

ok AC

Test #4:

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

input:

30
8 15
8 16
8 17
8 18
8 19
8 20
8 21
8 22
8 23
8 24
8 25
8 26
8 27
8 28
8 29
8 30
8 31
8 32
8 33
8 34
8 35
8 36
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9

output:

0 1 2 3 4 5 6 7 12 13 14 15 30 31 255 
0 1 2 3 4 5 6 7 248 249 250 251 252 253 254 255 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 255 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 254 255 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 30 31 255 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 252 253 254 255 
0 1 2 3 4 5 6 7 8 ...

result:

ok AC

Test #5:

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

input:

30
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
9 21
9 22
9 23
9 24
9 25
9 26
9 27
9 28
9 29
9 30
9 31
9 32
9 33
9 34
9 35
9 36
9 37
9 38
9 39

output:

0 1 2 3 4 5 6 7 510 511 
0 1 2 3 4 5 6 7 14 15 511 
0 1 2 3 4 5 6 7 508 509 510 511 
0 1 2 3 4 5 6 7 12 13 14 15 511 
0 1 2 3 4 5 6 7 12 13 14 15 510 511 
0 1 2 3 4 5 6 7 12 13 14 15 30 31 511 
0 1 2 3 4 5 6 7 504 505 506 507 508 509 510 511 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 511 
0 1 2 3 4 5 6 ...

result:

ok AC

Test #6:

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

input:

6
9 40
9 41
9 42
9 43
9 44
9 45

output:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 504 505 506 507 508 509 510 511 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 56 57 58 59 60 61 62 63 511 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2...

result:

ok AC

Test #7:

score: -100
Time Limit Exceeded

input:

30
60 1801
60 1802
60 1803
60 1804
60 1805
60 1806
60 1807
60 1808
60 1809
60 1810
60 1811
60 1812
60 1813
60 1814
60 1815
60 1816
60 1817
60 1818
60 1819
60 1820
60 1821
60 1822
60 1823
60 1824
60 1825
60 1826
60 1827
60 1828
60 1829
60 1830

output:

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

result: