QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #423892 | #8174. Set Construction | Iratis | WA | 1ms | 4140kb | C++14 | 2.8kb | 2024-05-28 18:55:52 | 2024-05-28 18:55:53 |
Judging History
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)
{
if(m==2)cout<<"0 63";
if(m==3)cout<<"0 1 63";
if(m==4)cout<<"0 1 3 63";
if(m==5)cout<<"0 1 2 3 63";
if(m==6)cout<<"0 1 2 3 7 63";
if(m==7)cout<<"0 1 3 4 5 7 63";
if(m==8)cout<<"0 1 3 4 5 7 15 63";
if(m==9)cout<<"0 1 2 3 4 5 6 7 63";
if(m==10)cout<<"0 1 2 3 4 5 6 7 15 63";
if(m==11)cout<<"0 1 2 3 7 8 9 10 11 15 63";
if(m==12)cout<<"0 1 2 3 7 8 9 10 11 15 31 63";
if(m==13)cout<<"0 1 3 4 5 7 8 9 11 12 13 15 63";
if(m==14)cout<<"0 1 3 4 5 7 8 9 11 12 13 15 31 63";
if(m==15)cout<<"0 1 3 4 5 7 15 16 17 19 20 21 23 31 63";
if(m==16)cout<<"0 1 2 3 4 5 6 7 9 11 13 15 22 23 31 63";
if(m==17)cout<<"0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 63";
if(m==18)cout<<"0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 31 63";
if(m==19)cout<<"0 1 2 3 4 5 6 7 15 16 17 18 19 20 21 22 23 31 63";
if(m==20)cout<<"0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 23 31 47 63";
if(m==21)cout<<"0 1 2 3 7 8 9 10 11 15 16 17 18 19 23 24 25 26 27 31 63";
cout<<'\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: 3964kb
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
Wrong Answer
time: 1ms
memory: 4140kb
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 1 63 0 1 3 63 0 1 2 3 63 0 1 2 3 7 63 0 1 3 4 5 7 63 0 1 3 4 5 7 15 63 0 1 2 3 4 5 6 7 63 0 1 2 3 4 5 6 7 15 63 0 1 2 3 7 8 9 10 11 15 63 0 1 2 3 7 8 9 10 11 15 31 63 0 1 3 4 5 7 8 9 11 12 13 15 63 0 1 3 4 5 7 8 9 11 12 13 15 31 63 0 1 3 4 5 7 15 16 17 19 20 21 23 31 63 0 1 2 3 ...
result:
wrong answer 63 is not in A