fork download 
  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_opt[26];  
  19.  
  20. void precompute() {
  21. 	for (int i = 1; i <= n; i++) {
  22. 		h_val[i] = rng(); 
  23. 	}
  24. }
  25.  
  26. void backtrack(int i, ll cur_h, vector<int>& ans) {
  27. 	if (cur_h == 0) {
  28. 		cout << ans.size() << '\n'; 
  29. 		for (int x : ans) cout << x << ' ';  
  30. 		exit(0); 
  31. 	}
  32.  
  33. 	if (i == m + 1) return; 
  34.  
  35. 	backtrack(i + 1, cur_h, ans); 
  36.  
  37. 	ans.push_back(i); 
  38. 	backtrack(i + 1, cur_h ^ h_opt[i], ans); 
  39. 	ans.pop_back(); 
  40. }
  41.  
  42. int main() {
  43. 	ios::sync_with_stdio(false); 
  44. 	cin.tie(nullptr); 	
  45. 	cin >> n >> m; 
  46.  
  47. 	precompute();  
  48.  
  49. 	ll cur_h = 0;  
  50. 	for (int i = 1; i <= n; i++) {
  51. 		int a; cin >> a; 
  52. 		if (a == 0) cur_h ^= h_val[i]; 
  53. 	}
  54.  
  55. 	for (int i = 1; i <= m; i++) {
  56. 		int l; cin >> l; 
  57. 		for (int j = 1; j <= l; j++) {
  58. 			int b; cin >> b; 
  59. 			h_opt[i] ^= h_val[b]; 
  60. 		}
  61. 	}
  62.  
  63. 	vector<int> ans; 
  64. 	backtrack(1, cur_h, ans);  
  65. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin 
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 
3
1 3 4
https://ideone.com/dKglnw
language:
C++14 (gcc 8.3)
created:
333 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!