QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393500 | #8174. Set Construction | i_am_noob | TL | 1ms | 3876kb | C++14 | 1.5kb | 2024-04-18 17:29:41 | 2024-04-18 17:29:42 |
Judging History
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...