Submission #1319005

#TimeUsernameProblemLanguageResultExecution timeMemory
1319005hynmjNorela (info1cup18_norela)C++20
100 / 100
80 ms131660 KiB
#include <bits/stdc++.h>
#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

const long long N = 2e5 + 5;
const long long M = (1ll << 25) + 5;
int a[N];
int dp[M];
void solve()
{
    int n, m;
    cin >> n >> m;
    int sz, e;
    // vi[a];
    for (int j = 0; j < m; j++)
    {
        cin >> sz;
        int mask = 0;
        for (int i = 0; i < sz; i++)
        {
            cin >> e;
            a[j] |= 1ll << (e - 1);
        }
    }
    // for (int i = 0; i < m; i++)
    // {
    //     cout << a[i] << ' ';
    // }
    // cout << endl;
    // int m = __lg(m)+1;
    vector<int> answers;
    dp[0] = 0;
    int ans = 0;
    for (int i = 1; i < (1ll << (m)); i++)
    {
        int j = (i - 1) & i;
        int subset = i ^ j;
        dp[i] = dp[j] ^ a[__lg(subset)];

        // debug(i);
        // debug(j);
        // debug(subset);
        // debug(dp[j]);
        // debug(a[subset-1]);
        // debug(dp[i]);

        // cout << dp[j] << ' '<< a[subset-1] << endl;
        // cout << endl;
        // cout << i << ' '<<dp[i] << endl;
        // cout << endl;
        if ((dp[i] ^ ((1ll << (n)) - 1)) == 0)
        {
            answers.push_back(i);
            // break;
        }
    }
    sort(answers.begin(), answers.end(), [&](const int a, const int b) -> bool
         {
        int ca = __builtin_popcountll(a);
        int cb = __builtin_popcountll(b);
        if (ca == cb)
        {
            int mask;
            for (int i = 0; i < m;i++)
            {
                mask = 1ll << i;
                if (((mask & a)) && ((mask & b) == 0))
                    return 1;
                if (((mask & b)) && ((mask & a) == 0))
                    return 0;
            }
        }

        return (ca < cb); });
    ans = answers[0];
    int mask;
    vector<int> answer;
    for (int i = 0; i < m; i++)
    {
        mask = 1ll << i;
        if (mask & ans)
        {
            answer.push_back(i);
        }
    }

    cout << answer.size() << endl;
    for (auto i : answer)
        cout << i + 1 << ' ';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...