oj.uz

Submission #923456

# Submission time Handle Problem Language Result Execution time Memory
923456 2024-02-07T09:11:45 Z NValchanov Norela (info1cup18_norela) C++17
0 / 100
 24 ms 592 KB 
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN=64;
const int MAXM=25;

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

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

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

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

void check_current(int mask, int x)
{
    if(count_bits(x) == n)
    {
        if(!ans)
            fill_order(mask);
        else
        {
            if(count_bits(ans)>count_bits(mask))
                fill_order(mask);
            else if(count_bits(ans)==count_bits(mask))
            {
                int lampa=-1;
                vector<int>tmp;
                for(int i=0;i<m;i++)
                {
                    if(mask&(1<<i))
                    {
                        tmp.push_back(i+1);
                        int 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(int mask=0;mask<(1<<m);mask++)
    {
        int cur=0;
        for(int i=0;i<m;i++)
        {
            if(mask&(1<<i))
            {
                cur^=a[i];
            }
        }
        check_current(mask, cur);
    }
}

void print()
{
    int sz=count_bits(ans);
    cout<<sz<<endl;
    for(int 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 23 ms 592 KB Output is correct
2 Incorrect 24 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 592 KB Output is correct
2 Incorrect 24 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 592 KB Output is correct
2 Incorrect 24 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 592 KB Output is correct
2 Incorrect 24 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -