# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
689918 | divad | Norela (info1cup18_norela) | C++14 | 1055 ms | 320 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define NMAX 62
#define MMAX 26
using namespace std;
int n,m,q,x,ans;
bitset<NMAX> b[MMAX];
vector<int> sol;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
ans = -1;
for(int i = 1; i <= m; i++){
cin >> q;
for(int j = 1; j <= q; j++){
cin >> x;
b[i][x] = 1;
}
}
for(int i = 0; i < (1<<m); i++){
bitset<NMAX> all;
for(int j = 0; j < m; j++){
if(i&(1<<j)){
all ^= b[j+1];
}
}
if(all.count() == n){
if(ans == -1){
ans = i;
for(int j = 0; j < m; j++){
if(i&(1<<j)){
sol.push_back(j+1);
}
}
}else{
if(__builtin_popcount(ans) > __builtin_popcount(i)){
sol.clear();
for(int j = 0; j < m; j++){
if(i&(1<<j)){
sol.push_back(j+1);
}
}
ans = i;
}else if(__builtin_popcount(ans) == __builtin_popcount(i)){
vector<int> aux;
int ok = -1;
for(int j = 0; j < m; j++){
if(i&(1<<j)){
aux.push_back(j+1);
int pos = aux.size()-1;
if(ok == -1){
if(aux[pos] > sol[pos]){
ok = 0;
}else if(aux[pos] < sol[pos]){
ok = 1;
}
}
}
}
if(ok){
sol.clear();
for(auto it: aux){
sol.push_back(it);
}
ans = i;
}
}
}
}
}
cout << __builtin_popcount(ans) << "\n";
for(auto it: sol){
cout << it << " ";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |