Submission #1318975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318975		hynmj	Norela (info1cup18_norela)	C++20	0 / 100	0 ms	332 KiB

norela

#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 << 24) + 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;
    dp[0] = 0;
    int ans = -1;
    for (int i = 1; i < (1 << (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)
        {
            ans = i;
            // cout << ans << endl;
            break;
        }
    }
    if (ans == -1)
    {
        cout << -1;
        return;
    }
    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;
}

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