#include <bits/stdc++.h>
#define int long long
using namespace std;
bool be(int a, int b){
if(a == -1 || b == -1) return a != -1;
if(__builtin_popcountll(a) != __builtin_popcountll(b))
return __builtin_popcountll(a) < __builtin_popcountll(b);
for(int i = 0;; i++){
if((a & (1 << i)) != (b & (1 << i)))
return (a & (1 << i)) > (b & (1 << i));
}
assert(0);
return false;
}
map<int, int> gen(int l, vector<int> a){
map<int, int> M;
int n = a.size();
for(int i = 1; i < (1 << n); i++){
int v = 0;
for(int j = 0; j < n; j++){
if(i & (1 << j)) v ^= a[j];
}
if(M.count(v) == 0 || be(i, M[v])) M[v] = i;
}
return M;
}
int ok(int x, int y){
return be(x, y) ? x : y;
}
int32_t main() {
int n, m; cin >> n >> m;
vector<int> a;
for(int i = 0; i < m; i++){
int k; cin >> k; int flip = 0;
for(int j = 0; j < k; j++){
int v; cin >> v; flip |= 1 << v - 1;
}
a.push_back(flip);
}
vector<int> a1, a2;
for(int i = 0; i < min(m, 12LL); i++){
a1.push_back(a[i]);
}
for(int i = 12; i < min(m, 24LL); i++){
a2.push_back(a[i]);
}
map<int, int> m1 = gen(0, a1), m2 = gen(a1.size(), a2);
int ans = -1;
int sum = (1LL << n) - 1;
if(m1.count(sum)) ans = ok(ans, m1[sum]);
if(m2.count(sum)) ans = ok(ans, m2[sum]);
for(auto i : m1){
int v = i.first, s = i.second;
if(m2.count(sum - v)){
ans = ok(ans, s | (m2[sum - v] << 12));
}
}
int c = 0;
for(int i = 0; i < m; i++){
if(ans & (1 << i)) c++;
}
cout << c << endl;
for(int i = 0; i < m; i++){
if(ans & (1 << i)) cout << i + 1 << ' ';
}
cout << endl;
}
Compilation message
norela.cpp: In function 'int32_t main()':
norela.cpp:40:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
40 | int v; cin >> v; flip |= 1 << v - 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
