제출 #1318990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318990		hynmj	Norela (info1cup18_norela)	C++20	0 / 100	4 ms	4408 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;
    vector<int> answers;
    dp[0] = 0;
    int ans = 0;
    for (int i = 1; i < (1 << (m + 1)); 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)
         {
        int ca = __builtin_popcountll(a);
        int cb = __builtin_popcountll(b);
        if (ca== cb)
            return a < b;
        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;
}

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