Submission #1289765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289765		erkam	Norela (info1cup18_norela)	C++20	100 / 100	49 ms	580 KiB

norela

#include <iostream>

using namespace std;

int n, m;
int ans;
long long arr[25];
long long goal;

void solve(int cur_index, long long cur_mask, long long cur_ans) {
    if (cur_mask == goal) {
        if (__builtin_popcountll(cur_ans) < __builtin_popcountll(ans)) {
            ans = cur_ans;
        } else if (__builtin_popcountll(cur_ans) == __builtin_popcountll(ans) && cur_ans > ans) {
            ans = cur_ans;
        }
    }
    if (cur_index == m) {
        return;
    }
    solve(cur_index + 1, cur_mask ^ arr[cur_index], cur_ans + (1ll << (m-cur_index-1)));
    solve(cur_index + 1, cur_mask, cur_ans);   
}

int main() {
    cin >> n >> m;
    ans = (1ll << m) - 1;
    goal = (1ll << n) - 1;
    for(int i = 0; i < m; i++) {
        int q; cin >> q;
        for(int j = 0; j < q; j++) {
            int x; cin >> x;
            arr[i] += 1ll << (x-1);
        }
    }
    solve(0, 0, 0);
    cout << __builtin_popcountll(ans) << endl;
    for(int i = 1; i <= m; i++) {
        if (ans & (1ll << (m-i))) {
            cout << i << " ";
        }
    }
    cout << endl;
}

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