Submission #95343

#	Time	Username	Problem	Language	Result	Execution time	Memory
95343		dalgerok	Norela (info1cup18_norela)	C++14	100 / 100	65 ms	504 KiB

norela

#include<bits/stdc++.h>
#define int long long
using namespace std;


const int N = 30;



int n, m, a[N], ans, need;

inline int f(int x){
    return __builtin_popcountll(x);
}

inline int cmp(int x, int y){
    if(f(x) < f(y)){
        return x;
    }
    if(f(x) > f(y)){
        return y;
    }
    for(int i = 0; i < m; i++){
        int a = ((x >> i) & 1), b = ((y >> i) & 1);
        if(a > b){
            return x;
        }
        if(a < b){
            return y;
        }
    }
    return x;
}

void rec(int pos = 0, int mask = 0, int sum = 0){
    if(mask == need){
        ans = cmp(ans, sum);
        return;
    }
    if(pos == m){
        return;
    }
    rec(pos + 1, mask, sum);
    rec(pos + 1, (mask ^ a[pos]), (sum | (1LL << pos)));
}

main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x;
        for(int j = 0; j < x; j++){
            cin >> y;
            a[i] |= (1LL << (y - 1));
        }
    }
    need = (1LL << n) - 1;
    ans = (1LL << m) - 1;
    rec();
    cout << f(ans) << "\n";
    for(int i = 0; i < m; i++){
        if((ans >> i) & 1){
            cout << i + 1 << " ";
        }
    }
}

Compilation message (stderr)

norela.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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