Submission #97906

#	Time	Username	Problem	Language	Result	Execution time	Memory
97906		314rate	Norela (info1cup18_norela)	C++14	0 / 100	3 ms	512 KiB

norela

#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 (stderr)

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++)
                     ~^~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25