Submission #674114

#TimeUsernameProblemLanguageResultExecution timeMemory
674114QwertyPiNorela (info1cup18_norela)C++14
0 / 100
2 ms468 KiB
#include <bits/stdc++.h> #define int long long using namespace std; bool be(int a, int b){ if(a == -1 || b == -1) return a != -1; if(__builtin_popcountll(a) != __builtin_popcountll(b)) return __builtin_popcountll(a) < __builtin_popcountll(b); for(int i = 0;; i++){ if((a & (1 << i)) != (b & (1 << i))) return (a & (1 << i)) > (b & (1 << i)); } assert(0); return false; } map<int, int> gen(int l, vector<int> a){ map<int, int> M; int n = a.size(); for(int i = 1; i < (1 << n); i++){ int v = 0; for(int j = 0; j < n; j++){ if(i & (1 << j)) v ^= a[j]; } if(M.count(v) == 0 || be(i, M[v])) M[v] = i; } return M; } int ok(int x, int y){ return be(x, y) ? x : y; } int32_t main() { int n, m; cin >> n >> m; vector<int> a; for(int i = 0; i < m; i++){ int k; cin >> k; int flip = 0; for(int j = 0; j < k; j++){ int v; cin >> v; flip |= 1 << v - 1; } a.push_back(flip); } vector<int> a1, a2; for(int i = 0; i < min(m, 12LL); i++){ a1.push_back(a[i]); } for(int i = 12; i < min(m, 24LL); i++){ a2.push_back(a[i]); } map<int, int> m1 = gen(0, a1), m2 = gen(a1.size(), a2); int ans = -1; int sum = (1LL << n) - 1; if(m1.count(sum)) ans = ok(ans, m1[sum]); if(m2.count(sum)) ans = ok(ans, m2[sum]); for(auto i : m1){ int v = i.first, s = i.second; if(m2.count(sum - v)){ ans = ok(ans, s | (m2[sum - v] << 12)); } } int c = 0; for(int i = 0; i < m; i++){ if(ans & (1 << i)) c++; } cout << c << endl; for(int i = 0; i < m; i++){ if(ans & (1 << i)) cout << i + 1 << ' '; } cout << endl; }

Compilation message (stderr)

norela.cpp: In function 'int32_t main()':
norela.cpp:40:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   40 |    int v; cin >> v; flip |= 1 << v - 1;
      |                                  ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...