Submission #861508

#TimeUsernameProblemLanguageResultExecution timeMemory
861508Alfraganus"The Lyuboyn" code (IZhO19_lyuboyn)C++14
52 / 100
74 ms35280 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define fs first #define ss second #define str string #define all(a) a.begin(), a.end() #define print(a) \ for (auto x : a) \ cout << x << ' '; \ cout << endl; #define each(x, a) for (auto x : a) vector<int> ans; vector<bool> used; int n, k, t, sx = 0; bool good(int s1, int s2) { int ans = 0; while (s1 > 0 or s2 > 0) { ans += (s1 % 2 != s2 % 2); s1 /= 2; s2 /= 2; } return ans == k; } bool dfs(int node, int step) { if (step == (1 << n) - 1) { if (t == 0) { ans.push_back(node); return true; } if (good(sx, node)) ans.push_back(node); else return false; return true; } used[node] = 1; if (k == 1) { int x = node; for (int i = 0; i < n; i++) { x ^= (1 << i); if (!used[x] and dfs(x, step + 1)) { ans.push_back(node); return true; } x ^= (1 << i); } } else if (k == 3) { int y = node; for (int i = 0; i < n; i++) { y ^= (1 << i); for (int j = i + 1; j < n; j++) { y ^= (1 << j); for (int x = j + 1; x < n; x++) { y ^= (1 << x); if (!used[y] and dfs(y, step + 1)) { ans.push_back(node); return true; } y ^= (1 << x); } y ^= (1 << j); } y ^= (1 << i); } } else if (k == 5) { int y = node; for (int i = 0; i < n; i++) { y ^= (1 << i); for (int j = i + 1; j < n; j++) { y ^= (1 << j); for (int x = j + 1; x < n; x++) { y ^= (1 << x); for (int i1 = x + 1; i1 < n; i1++) { y ^= (1 << i1); for (int i2 = i1 + 1; i2 < n; i2++) { y ^= (1 << i2); if (!used[((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)] and dfs(((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2), step + 1)) { ans.push_back(node); return true; } y ^= (1 << i2); } y ^= (1 << i1); } y ^= (1 << x); } y ^= (1 << j); } y ^= (1 << i); } } else if (k == 7) { int y = node; for (int i = 0; i < n; i++) { y ^= (1 << i); for (int j = i + 1; j < n; j++) { y ^= (1 << j); for (int x = j + 1; x < n; x++) { y ^= (1 << x); for (int i1 = x + 1; i1 < n; i1++) { y ^= (1 << i1); for (int i2 = i1 + 1; i2 < n; i2++) { y ^= (1 << i2); for (int i3 = i2 + 1; i3 < n; i3++) { y ^= (1 << i3); for (int i4 = i3 + 1; i4 < n; i4++) { y ^= (1 << i4); if (!used[y] and dfs(y, step + 1)) { ans.push_back(node); return true; } y ^= (1 << i4); } y ^= (1 << i3); } y ^= (1 << i2); } y ^= (1 << i1); } y ^= (1 << x); } y ^= (1 << j); } y ^= (1 << i); } } used[node] = 0; return false; } void solve() { cin >> n >> k >> t; str s; cin >> s; for (int i = s.size() - 1; i >= 0; i--) { if (s[i] == '1') { sx += (1 << (s.size() - 1 - i)); } } if (k % 2 == 0 or k == 9 or n == k) { cout << -1; return; } bool flag = 2 * k > n; if (2 * k > n) k = n - k; if(k % 2 == 0 or (flag and sx != 0)){ cout << -1; return; } used.resize((1 << n)); if (dfs(sx, 0)) { cout << (1 << n) << endl; if(flag){ reverse(all(ans)); for(int i = 0; i < ans.size(); i ++){ str s = ""; if((i & 1)){ for(int j = 0; j < n; j ++){ if(ans[i] % 2 == 0) s += '1'; else s += '0'; ans[i] /= 2; } cout << s << endl; } else{ for (int j = 0; j < n; j++) { if (ans[i] % 2 == 0) s += '0'; else s += '1'; ans[i] /= 2; } cout << s << endl; } } } else{ reverse(all(ans)); for (int i = 0; i < ans.size(); i++) { str s = ""; for (int j = 0; j < n; j++) { if (ans[i] % 2 == 0) s += '0'; else s += '1'; ans[i] >>= 1; } reverse(all(s)); cout << s << endl; } } } else { cout << -1; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); cout << endl; } }

Compilation message (stderr)

lyuboyn.cpp: In function 'void solve()':
lyuboyn.cpp:197:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |             for(int i = 0; i < ans.size(); i ++){
      |                            ~~^~~~~~~~~~~~
lyuboyn.cpp:224:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |             for (int i = 0; i < ans.size(); i++)
      |                             ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...