QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423887#8174. Set ConstructionIratisTL 1ms3860kbC++141.9kb2024-05-28 18:51:372024-05-28 18:51:37

Judging History

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

  • [2024-05-28 18:51:37]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3860kb
  • [2024-05-28 18:51:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

bool ST;

int n,m,S;

namespace Force
{
	vector<int>a,ans;bool vst[1<<16],fg;
	inline void check()
	{
		if((int)a.size()!=m)return ;
		for(int x:a)for(int y:a)if(!vst[x&y]||!vst[x|y])return ;ans=a;fg=1;
	}
	void dfs(int k)
	{
		if(k==S){check();return ;}
		if((int)a.size()+1<=m)a.push_back(k),vst[k]=1,dfs(k+1),a.pop_back(),vst[k]=0;if(fg)return ;
		if(k>0&&k<S-1)dfs(k+1);
	}
	inline void main(){if(m==2){cout<<0<<' '<<S-1<<'\n';return ;}fg=0,dfs(0);for(int x:ans)cout<<x<<' ';cout<<'\n';}
};

vector<int>ans;
inline void solve()
{
	cin>>n>>m,S=(1ll<<n);if(n<=5||m==2){Force::main();return ;}ans.clear(),ans.push_back(0);int tmp=m;m--;
	int x=0;vector<int>op;while(m>1){if(m&1)op.push_back(1),m--;else op.push_back(2),m/=2;}reverse(op.begin(),op.end());
	for(int o:op)
	{
		if(o==1)x++,ans.push_back((1ll<<x)-1);
		else {vector<int>t=ans;for(int w:t)ans.push_back(w|(1ll<<x));x++;}
	}
	if(ans.back()!=S-1)
	{
		ans.push_back(S-1);for(int x:ans)cout<<x<<' ';cout<<'\n';
		return ;
	}
	if(n==6&&m==16){cout<<"0 7 8 15 16 23 24 31 32 39 40 47 48 55 56 63\n";return ;}
	if(n==7&&m==24){cout<<"0 7 15 16 23 31 32 39 47 48 55 63 64 71 79 80 87 95 96 103 111 112 119 127\n";return ;}
	if(n==7&&m==28){cout<<"0 3 7 8 11 15 31 32 35 39 40 43 47 63 64 67 71 72 75 79 95 96 99 103 104 107 111 127\n";return ;}
	if(n==8&&m==32){cout<<"0 15 16 31 32 47 48 63 64 79 80 95 96 111 112 127 128 143 144 159 160 175 176 191 192 207 208 223 224 239 240 255\n";return ;}
	m=tmp,Force::main();
}

bool ED;

signed main()
{
	int time_st=clock();
	cerr<<(&ST-&ED)/1024.0/1024<<endl;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T;cin>>T;while(T--)solve();
	cerr<<(clock()-time_st)/1e6<<endl;return 0;
}

詳細信息

Test #1:

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

input:

3
3 5
4 8
60 2

output:

0 1 2 3 7 
0 1 2 3 5 7 11 15 
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: