QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408286 | #8174. Set Construction | Network_Error | TL | 0ms | 3528kb | C++14 | 1.5kb | 2024-05-09 23:11:05 | 2024-05-09 23:11:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define piii tuple<int,int,int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr<<#var<<'='<<(var)<<"; "
#define int long long
int n,m;
map<int,bool> vis;
vector<int> st,ans;
bool chk(){
for(auto s:st)
for(auto t:st)
if(s<t&&(!vis[s|t]||!vis[s&t]))return 0; return 1;
}
bool dfs(int i,int n,int m){
if(st.size()>m)return 0;
if(i>=(1ll<<n)-1){
if(st.size()==m&&chk())return ans=st,1;return 0;
}
if(dfs(i+1,n,m))return 1;
if(st.size()>=m)return 0;
st.pb(i),vis[i]=1;
if(dfs(i+1,n,m))return 1;
st.pop_back(),vis[i]=0;return 0;
}
vector<int> sol(int n,int m){
if(n<=5){
vis[0]=vis[(1ll<<n)-1]=1;
st.pb(0),st.pb((1ll<<n)-1);
dfs(1,n,m);
// deb(ans.size()),deb(n),deb(m)<<'\n';
return ans;
}
if(m<=n*(n-1)/2){
auto ans=sol(n-1,m);
for(auto &x:ans){
x<<=1;
if(x+2==(1ll<<n))x++;
} return ans;
}
if(~m&1){
auto ans=sol(n-1,m/2);
vector<int> res(0);
for(auto &x:ans)res.pb(x<<1),res.pb(x<<1|1);
return res;
}
if(m&1){
auto ans=sol(n-1,m-1);
for(auto &x:ans)x=x<<1|1;
ans.pb(0); return ans;
}
}
void work(){
st.clear(),vis.clear(),ans.clear();
cin>>n>>m;
auto ans=sol(n,m);
for(auto x:ans)cout<<x<<' ';cout<<'\n';
}
signed main(){
ios::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
int T=1;cin>>T;while(T--)work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
input:
3 3 5 4 8 60 2
output:
0 7 4 5 6 0 15 4 8 10 12 13 14 0 1152921504606846975
result:
ok AC
Test #2:
score: -100
Time Limit Exceeded
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