QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393500#8174. Set Constructioni_am_noobTL 1ms3876kbC++141.5kb2024-04-18 17:29:412024-04-18 17:29:42

Judging History

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

  • [2024-04-18 17:29:42]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3876kb
  • [2024-04-18 17:29:41]
  • 提交

answer

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

using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())

const int N=405,mod=998244353;

int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int mul(int x, int y){return 1ll*x*y%mod;}
int Pow(int x, ll y=mod-2){int res=1; for(; y; y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}

int dp[2222];

vector<ll> get(int n, int m){
    if(m==2) return {0,(1ll<<n)-1};
    if(n==5&&m==15){
        vector<ll> a=get(2,3),b=get(3,5);
        vector<ll> res;
        for(auto i: a) for(auto j: b) res.pb((i<<3)+j);
        return res;
    }
    if(m&1){
        vector<ll> res=get(n-1,m-1);
        res.pb((1ll<<n)-1);
        return res;
    }
    vector<ll> res=get(n-1,m/2);
    for(int i=0; i<m/2; ++i) res.pb((1ll<<n-1)+res[i]);
    return res;
}

bool check(vector<ll> a){
    for(int i=0; i<sz(a); ++i) for(int j=i+1; j<sz(a); ++j){
        ll x=a[i]&a[j];
        if(!binary_search(all(a),x)) return false;
        x=a[i]|a[j];
        if(!binary_search(all(a),x)) return false;
    }
    return true;
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n,m; cin >> n >> m;
        vector<ll> res=get(n,m);
        sort(all(res));
        assert(check(res));
        for(auto i: res) cout << i << ' ';
        cout << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
3 5
4 8
60 2

output:

0 1 2 3 7 
0 3 4 7 8 11 12 15 
0 1152921504606846975 

result:

ok AC

Test #2:

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

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 31 63 
0 31 32 63 
0 15 16 31 63 
0 15 31 32 47 63 
0 7 15 16 23 31 63 
0 15 16 31 32 47 48 63 
0 7 8 15 16 23 24 31 63 
0 7 8 15 31 32 39 40 47 63 
0 3 4 7 15 16 19 20 23 31 63 
0 7 15 16 23 31 32 39 47 48 55 63 
0 3 7 8 11 15 16 19 23 24 27 31 63 
0 3 7 8 11 15 31 32 35 39 40 43 47 63 
0 1...

result:

ok AC

Test #3:

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

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 15 31 32 47 63 64 79 95 96 111 127 
0 7 15 16 23 31 32 39 47 48 55 63 127 
0 7 15 16 23 31 63 64 71 79 80 87 95 127 
0 3 7 8 11 15 31 32 35 39 40 43 47 63 127 
0 15 16 31 32 47 48 63 64 79 80 95 96 111 112 127 
0 7 8 15 16 23 24 31 32 39 40 47 48 55 56 63 127 
0 7 8 15 16 23 24 31 63 64 71 72 79 8...

result:

ok AC

Test #4:

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

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 7 15 16 23 31 63 64 71 79 80 87 95 127 255 
0 31 32 63 64 95 96 127 128 159 160 191 192 223 224 255 
0 15 16 31 32 47 48 63 64 79 80 95 96 111 112 127 255 
0 15 16 31 32 47 48 63 127 128 143 144 159 160 175 176 191 255 
0 7 8 15 16 23 24 31 63 64 71 72 79 80 87 88 95 127 255 
0 15 16 31 63 64 79 8...

result:

ok AC

Test #5:

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

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 63 64 127 255 256 319 320 383 511 
0 31 32 63 127 128 159 160 191 255 511 
0 63 127 128 191 255 256 319 383 384 447 511 
0 31 63 64 95 127 128 159 191 192 223 255 511 
0 31 63 64 95 127 255 256 287 319 320 351 383 511 
0 15 31 32 47 63 127 128 143 159 160 175 191 255 511 
0 63 64 127 128 191 192 2...

result:

ok AC

Test #6:

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

input:

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

output:

0 15 16 31 63 64 79 80 95 127 128 143 144 159 191 192 207 208 223 255 256 271 272 287 319 320 335 336 351 383 384 399 400 415 447 448 463 464 479 511 
0 7 8 15 31 32 39 40 47 63 64 71 72 79 95 96 103 104 111 127 128 135 136 143 159 160 167 168 175 191 192 199 200 207 223 224 231 232 239 255 511 
0 7...

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 140737488355327 281474976710655 281474976710656 422212465065983 562949953421311 1125899906842623 1125899906842624 1266637395197951 1407374883553279 1407374883553280 1548112371908607 1688849860263935 2251799813685247 2251799813685248 2392537302040575 2533274790395903 2533274790395904 26740122787512...

result: