Submission #1062161

#TimeUsernameProblemLanguageResultExecution timeMemory
1062161peraNorela (info1cup18_norela)C++17
100 / 100
358 ms394440 KiB
#include<bits/stdc++.h> using namespace std; main(){ int n , m; cin >> n >> m; long long M = (1LL << n) - 1; vector<long long> v(m); for(int i = 0;i < m;i ++){ int x; cin >> x; while(x--){ int y; cin >> y; --y; v[i] |= (1LL << y); } } vector<pair<long long , int>> u; u.emplace_back(make_pair(0LL , 0)); for(int i = 0;i < m;i ++){ vector<pair<long long , int>> e; for(auto [x , mask] : u){ e.emplace_back(make_pair(x ^ v[i] , mask | (1LL << i))); } for(auto [x , mask] : e){ u.emplace_back(make_pair(x , mask)); } } int best_mask = (1LL << (m + 1)) - 1; for(auto [x , mask] : u){ if(x != M){ continue; } if(__builtin_popcount(mask) < __builtin_popcount(best_mask)){ best_mask = mask; }else if(__builtin_popcount(mask) == __builtin_popcount(best_mask)){ int v = mask ^ best_mask; if(mask >> (__lg(v & -v)) & 1){ best_mask = mask; } } } cout << __builtin_popcount(best_mask) << endl; for(int i = 0;i < m;i ++){ if(best_mask >> i & 1){ cout << i + 1 << " "; } } cout << endl; }

Compilation message (stderr)

norela.cpp:3:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    3 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...