# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80848 | 2018-10-22T13:51:19 Z | farukkastamonuda | Norela (info1cup18_norela) | C++14 | 88 ms | 804 KB |
#include <bits/stdc++.h> #define fi first #define se second #define lo long long #define inf 1000000000 #define md 1000000007 #define li 2005 #define mp make_pair #define pb push_back using namespace std; int n, m, x, y; lo int ans, gg, ind[80]; lo int bet(lo int a, lo int b){ if(__builtin_popcount(a) < __builtin_popcount(b)) return a; if(__builtin_popcount(a) > __builtin_popcount(b)) return b; for(int i = 0;i < m; i ++){ int x = a&(1 << i); int y = b&(1 << i); if(x < y) return b; if(y < x) return a; } return a; } void dfs(int node, lo int msk, lo int ste){ if(msk == gg){ ans=bet(ans, ste); return ; } if(node == m + 1) return ; dfs(node + 1, msk ^ ind[node], ste ^ (1 << (node - 1))); dfs(node + 1, msk, ste); } int main(){ scanf("%d %d", &n, &m); gg = (1LL << n) - 1; ans = (1LL << m) - 1; for(int i = 1; i <= m; i ++){ scanf("%d", &x); for(int j = 1;j <= x; j ++){ scanf("%d", &y); y--; ind[i] ^= (1LL<<y); } } dfs(1, 0, 0); printf("%d\n", __builtin_popcount(ans)); for(int i = 0; i < m; i ++){ if(ans&(1 << i)) printf("%d ", i + 1); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 424 KB | Output is correct |
4 | Correct | 3 ms | 548 KB | Output is correct |
5 | Correct | 3 ms | 548 KB | Output is correct |
6 | Correct | 3 ms | 680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 424 KB | Output is correct |
4 | Correct | 3 ms | 548 KB | Output is correct |
5 | Correct | 3 ms | 548 KB | Output is correct |
6 | Correct | 3 ms | 680 KB | Output is correct |
7 | Correct | 7 ms | 680 KB | Output is correct |
8 | Correct | 12 ms | 680 KB | Output is correct |
9 | Correct | 12 ms | 680 KB | Output is correct |
10 | Correct | 12 ms | 680 KB | Output is correct |
11 | Correct | 15 ms | 680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 424 KB | Output is correct |
4 | Correct | 3 ms | 548 KB | Output is correct |
5 | Correct | 3 ms | 548 KB | Output is correct |
6 | Correct | 3 ms | 680 KB | Output is correct |
7 | Correct | 7 ms | 680 KB | Output is correct |
8 | Correct | 12 ms | 680 KB | Output is correct |
9 | Correct | 12 ms | 680 KB | Output is correct |
10 | Correct | 12 ms | 680 KB | Output is correct |
11 | Correct | 15 ms | 680 KB | Output is correct |
12 | Correct | 12 ms | 680 KB | Output is correct |
13 | Correct | 22 ms | 680 KB | Output is correct |
14 | Correct | 21 ms | 692 KB | Output is correct |
15 | Correct | 22 ms | 704 KB | Output is correct |
16 | Correct | 31 ms | 704 KB | Output is correct |
17 | Correct | 22 ms | 704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 424 KB | Output is correct |
4 | Correct | 3 ms | 548 KB | Output is correct |
5 | Correct | 3 ms | 548 KB | Output is correct |
6 | Correct | 3 ms | 680 KB | Output is correct |
7 | Correct | 7 ms | 680 KB | Output is correct |
8 | Correct | 12 ms | 680 KB | Output is correct |
9 | Correct | 12 ms | 680 KB | Output is correct |
10 | Correct | 12 ms | 680 KB | Output is correct |
11 | Correct | 15 ms | 680 KB | Output is correct |
12 | Correct | 12 ms | 680 KB | Output is correct |
13 | Correct | 22 ms | 680 KB | Output is correct |
14 | Correct | 21 ms | 692 KB | Output is correct |
15 | Correct | 22 ms | 704 KB | Output is correct |
16 | Correct | 31 ms | 704 KB | Output is correct |
17 | Correct | 22 ms | 704 KB | Output is correct |
18 | Correct | 43 ms | 724 KB | Output is correct |
19 | Correct | 41 ms | 724 KB | Output is correct |
20 | Correct | 81 ms | 724 KB | Output is correct |
21 | Correct | 88 ms | 804 KB | Output is correct |
22 | Correct | 80 ms | 804 KB | Output is correct |
23 | Correct | 81 ms | 804 KB | Output is correct |