| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 517194 |
2022-01-22T17:07:38 Z |
raid |
Norela (info1cup18_norela) |
C++17 |
|
71 ms |
300 KB |
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXM = 25;
using ll = long long;
#define bpc __builtin_popcount
ll v[MAXM], target;
int res_mask;
int m;
void backtrack( int idx, ll _xor, int mask ) {
if ( idx == m ) {
if ( _xor == target && (bpc(res_mask) > bpc(mask) || (bpc(res_mask) == bpc(mask) && res_mask < mask)) ) {
res_mask = mask;
}
return;
}
backtrack( idx + 1, _xor, mask );
backtrack( idx + 1, _xor ^ v[idx], mask + (1 << (m - idx - 1)) );
}
vector<int> sol;
int main() {
int n, x, p;
cin >> n >> m;
res_mask = target = (1ll << n) - 1;
for ( int i = 0; i < m; ++i ) {
cin >> x;
while (x--) {
cin >> p;
v[i] += (1ll << (p-1));
}
}
backtrack( 0, 0ll, 0 );
for ( int i = 0; i < m; ++i ) {
if ( res_mask & (1 << (m - i - 1)) ) {
sol.push_back( i );
}
}
cout << sol.size() << "\n";
for ( int i = 0; i < sol.size(); ++i ) {
cout << sol[i] + 1 << " ";
}
return 0;
}
Compilation message
norela.cpp: In function 'int main()':
norela.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for ( int i = 0; i < sol.size(); ++i ) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Correct |
2 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
208 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Correct |
2 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
208 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Correct |
5 ms |
296 KB |
Output is correct |
| 8 |
Correct |
10 ms |
208 KB |
Output is correct |
| 9 |
Correct |
10 ms |
292 KB |
Output is correct |
| 10 |
Correct |
9 ms |
300 KB |
Output is correct |
| 11 |
Correct |
9 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Correct |
2 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
208 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Correct |
5 ms |
296 KB |
Output is correct |
| 8 |
Correct |
10 ms |
208 KB |
Output is correct |
| 9 |
Correct |
10 ms |
292 KB |
Output is correct |
| 10 |
Correct |
9 ms |
300 KB |
Output is correct |
| 11 |
Correct |
9 ms |
208 KB |
Output is correct |
| 12 |
Correct |
9 ms |
296 KB |
Output is correct |
| 13 |
Correct |
18 ms |
208 KB |
Output is correct |
| 14 |
Correct |
17 ms |
208 KB |
Output is correct |
| 15 |
Correct |
17 ms |
296 KB |
Output is correct |
| 16 |
Correct |
18 ms |
208 KB |
Output is correct |
| 17 |
Correct |
20 ms |
296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Correct |
2 ms |
292 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
208 KB |
Output is correct |
| 6 |
Correct |
2 ms |
208 KB |
Output is correct |
| 7 |
Correct |
5 ms |
296 KB |
Output is correct |
| 8 |
Correct |
10 ms |
208 KB |
Output is correct |
| 9 |
Correct |
10 ms |
292 KB |
Output is correct |
| 10 |
Correct |
9 ms |
300 KB |
Output is correct |
| 11 |
Correct |
9 ms |
208 KB |
Output is correct |
| 12 |
Correct |
9 ms |
296 KB |
Output is correct |
| 13 |
Correct |
18 ms |
208 KB |
Output is correct |
| 14 |
Correct |
17 ms |
208 KB |
Output is correct |
| 15 |
Correct |
17 ms |
296 KB |
Output is correct |
| 16 |
Correct |
18 ms |
208 KB |
Output is correct |
| 17 |
Correct |
20 ms |
296 KB |
Output is correct |
| 18 |
Correct |
36 ms |
272 KB |
Output is correct |
| 19 |
Correct |
37 ms |
208 KB |
Output is correct |
| 20 |
Correct |
71 ms |
208 KB |
Output is correct |
| 21 |
Correct |
68 ms |
208 KB |
Output is correct |
| 22 |
Correct |
68 ms |
276 KB |
Output is correct |
| 23 |
Correct |
68 ms |
276 KB |
Output is correct |
