# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70427 | MrTEK | Norela (info1cup18_norela) | C++14 | 92 ms | 792 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>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'
#define bit __builtin_popcount
typedef long long int ll;
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 65;
const int M = 26;
const int SQ = 350;
const int MOD = 998244353;
typedef long long int lli;
typedef pair<int,int> pii;
vector <int> v[N];
int n,m;
ll tar,ans,a[N];
int my_min(int x,int y) {
if (bit(x) < bit(y)) return x;
if (bit(x) > bit(y)) return y;
for (int i = 0 ; i < m ; i++) {
int a = x & (1 << i) , b = y & (1 << i);
if (a > b) return x;
if (a < b) return y;
}
return x;
}
void brute(int cur,ll mask,int sum) {
if (mask == tar) {
ans = my_min(ans,sum);
return;
}
if (cur == m) return ;
brute(cur + 1,mask,sum);
brute(cur + 1,mask ^ a[cur], sum + (1 << cur));
}
int main() {
scanf("%d %d",&n,&m);
tar = (1ll << n) - 1;
ans = (1ll << m) - 1;
for (int i = 0 ; i < m ; i++) {
int q;
scanf("%d",&q);
for (int j = 1 ; j <= q ; j++) {
int x;
scanf("%d",&x);
a[i] = a[i] ^ (1ll << (x - 1));
}
}
brute(0,0,0);
printf("%d\n",bit(ans));
for (int i = 0 ; i < m ; i++) {
if ((1 << i) & ans)
printf("%d ",i + 1);
}
}
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... |