oj.uz

Submission #923458

# Submission time Handle Problem Language Result Execution time Memory
923458 2024-02-07T09:14:18 Z NValchanov Norela (info1cup18_norela) C++17
0 / 100
 16 ms 348 KB 
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const ll MAXN=64;
const ll MAXM=25;

ll a[MAXN],n,m,q,c;
ll ans;
vector<ll>order;

void read()
{
    cin>>n>>m;
    for(ll i=0;i<m;i++)
    {
        cin>>q;
        for(ll j=0;j<q;j++)
        {
            cin>>c;
            a[i]|=(ll)(1LL<<(c-1));
        }
    }
}

ll count_bits(ll mask)
{
    ll cnt=0;
    for(ll i=0;i<n;i++)
    {
        if(mask&(1LL<<i))
            cnt++;
    }
    return cnt;
}


void fill_order(ll mask)
{
    order.clear();
    ans=mask;
    for(ll i=0;i<m;i++)
    {
        if(mask&(1LL<<(i)))
        {
            order.push_back(i+1);
        }
    }
}

void check_current(ll mask, ll x)
{
    if(__builtin_popcount(x) == n)
    {
        if(!ans)
            fill_order(mask);
        else
        {
            if(__builtin_popcount(ans)>__builtin_popcount(mask))
                fill_order(mask);
            else if(__builtin_popcount(ans)==__builtin_popcount(mask))
            {
                ll lampa=-1;
                vector<ll>tmp;
                for(ll i=0;i<m;i++)
                {
                    if(mask&(1LL<<i))
                    {
                        tmp.push_back(i+1);
                        ll sz=tmp.size();
                        if(lampa==-1)
                        {
                            if(tmp[sz-1]>order[sz-1])
                                lampa=0;
                            else if(tmp[sz-1]<order[sz-1])
                                lampa=1;
                        }
                    }
                }
                if(lampa==1)
                {
                    ans=mask;
                    order.clear();
                    order=tmp;
                }
            }
        }
    }
}

void solve()
{
    ans=0;
    for(ll mask=0;mask<(1LL<<m);mask++)
    {
        ll cur=0;
        for(ll i=0;i<m;i++)
        {
            if(mask&(1LL<<i))
            {
                cur^=a[i];
            }
        }
        check_current(mask, cur);
    }
}

void print()
{
    ll sz=__builtin_popcount(ans);
    cout<<sz<<endl;
    for(ll i=0;i<sz;i++)
    {
        cout<<order[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    #ifdef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    read();
    solve();
    print();

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Incorrect 16 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Incorrect 16 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Incorrect 16 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Incorrect 16 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -