fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // mt19937_64 rng(time(0)) 
  12.  
  13. const int N = 1e4 + 5; 
  14.  
  15. int n, m; 
  16.  
  17. ll h_val[N]; 
  18. ll h_op[26];  
  19.  
  20. void precompute() {
  21. 	for (int i = 1; i <= n; i++) h_val[i] = rng(); 
  22. }
  23.  
  24. void backtrack(int i, ll cur_h, vector<int>& ans) {
  25. 	if (cur_h == 0) {
  26. 		cout << ans.size() << '\n'; 
  27. 		for (int x : ans) cout << x << ' ';  
  28. 		exit(0); 
  29. 	}
  30.  
  31. 	if (i == m + 1) return; 
  32.  
  33. 	backtrack(i + 1, cur_h, ans); 
  34.  
  35. 	ans.push_back(i); 
  36. 	backtrack(i + 1, cur_h ^ h_op[i], ans); 
  37. 	ans.pop_back(); 
  38. }
  39.  
  40. int main() {
  41. 	ios::sync_with_stdio(false); 
  42. 	cin.tie(nullptr); 	
  43. 	cin >> n >> m; 
  44.  
  45. 	precompute();  
  46.  
  47. 	ll cur_h = 0;  
  48. 	for (int i = 1; i <= n; i++) {
  49. 		int a; cin >> a; 
  50. 		if (a == 0) cur_h ^= h_val[i]; 
  51. 	}
  52.  
  53. 	for (int i = 1; i <= m; i++) {
  54. 		int l; cin >> l; 
  55. 		for (int j = 1; j <= l; j++) {
  56. 			int b; cin >> b; 
  57. 			h_op[i] ^= h_val[b]; 
  58. 		}
  59. 	}
  60.  
  61. 	vector<int> ans; 
  62. 	backtrack(1, cur_h, ans);  
  63. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6 5
0 0 0 0 0 0
3 2 4 6
5 1 2 3 4 5
3 2 3 5
2 1 2
2 2 6
stdout
copy 
3
1 3 4
https://ideone.com/eJCm0i
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!