#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
int m;
ll a[100];
ll tot;
bool operator < (vector<int>a,vector<int>b)
{
if(a.size()!=b.size())
{
return a.size()<b.size();
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for(int i=0;i<a.size();i++)
{
if(a[i]!=b[i])
{
return (a[i]<b[i]);
}
}
return (a.size()<b.size());
}
vector<int> operator + (vector<int>a,vector<int>b)
{
vector<int>r=a;
for(auto &x:b)
{
r.push_back(x);
}
sort(r.begin(),r.end());
return r;
}
map<ll,vector<int>>res1;
map<ll,vector<int>>res2;
int pivot;
vector<int>st;
void go1(int cur,ll mask)
{
if(cur>pivot)
{
if(res1[mask].size()==0)
{
res1[mask]=st;
}
else
{
if(st<res1[mask])
{
res1[mask]=st;
}
}
}
else
{
go1(cur+1,mask);
st.push_back(cur);
go1(cur+1,(mask^a[cur]));
st.pop_back();
}
}
void go2(int cur,ll mask)
{
if(cur>m)
{
if(res2[mask].size()==0)
{
res2[mask]=st;
}
else
{
if(st<res2[mask])
{
res2[mask]=st;
}
}
}
else
{
go2(cur+1,mask);
st.push_back(cur);
go2(cur+1,(mask^a[cur]));
st.pop_back();
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input","r",stdin);
// freopen("output","w",stdout);
cin>>n>>m;
tot=(1LL<<n)-1LL;
for(int i=1;i<=m;i++)
{
int l,x;
cin>>l;
for(int j=1;j<=l;j++)
{
cin>>x;
x--;
a[i]+=(1LL<<x);
}
}
pivot=m/2;
/// 1, 2, ..., pivot
/// pivot + 1, pivot + 2, ... , m
go1(1,0LL);
go2(pivot+1,0LL);
vector<int>ans;
if(res1[tot].size()>0)
{
ans=res1[tot];
}
/// cout<<" : "<<res1[0].size()<<"\n";
for(auto &kek:res1)
{
ll a=kek.first;
ll b=(tot^a);
if(res1[a].size()>0 && res2[b].size()>0)
{
vector<int>k=res1[a]+res2[b];
if(ans.size()==0)
{
ans=k;
}
else
{
if(k<ans)
{
ans=k;
}
}
/// cout<<"= "<<a<<" , "<<b<<"\n";
}
/// cout<<" = "<<a<<"\n";
}
cout<<ans.size()<<"\n";
for(auto &it:ans)
{
cout<<it<<" ";
}
cout<<"\n";
return 0;
}
/**
cc
**/
Compilation message
norela.cpp: In function 'bool operator<(std::vector<int>, std::vector<int>)':
norela.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
