QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408286#8174. Set ConstructionNetwork_ErrorTL 0ms3528kbC++141.5kb2024-05-09 23:11:052024-05-09 23:11:06

Judging History

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

  • [2024-05-09 23:11:06]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3528kb
  • [2024-05-09 23:11:05]
  • 提交

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

output:


result: