Submission #899083

#TimeUsernameProblemLanguageResultExecution timeMemory
899083vjudge1"The Lyuboyn" code (IZhO19_lyuboyn)C++17
34 / 100
1026 ms6392 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int Z = 10000; mt19937 rng(time(nullptr)); int n, k, t, s; string ss; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> t >> ss; if (k%2 == 0) { cout << "-1\n"; return 0; } s = 0; while (ss.size() < n) ss = "0"+ss; for (int i = 0; i < n; i++) { s += (1 << (n-i-1)) * (ss[i] == '1'); } if (n <= 4) { for (int zz = 0; zz < Z; zz++) { vector<int> ans(1 << n); for (int i = 0; i < (1 << n); i++) { ans[i] = i; if (i == s) swap(ans[0], ans[i]); } bool ok = 0; shuffle(ans.begin()+1, ans.end(), rng); for (int z = 0; z < Z; z++) { int x = -1; for (int i = 0; i+1 < (1 << n); i++) { if (__builtin_popcount(ans[i] ^ ans[i+1]) != k) { x = i; break; } } if (x == -1) { ok = 1; break; } int y = -1; for (int i = x+2; i+1 < (1 << n); i++) { if (__builtin_popcount(ans[i] ^ ans[i+1]) != k && __builtin_popcount(ans[x] ^ ans[i]) == k && __builtin_popcount(ans[x+1] ^ ans[i+1]) == k) { y = i; break; } } if (y == -1) break; reverse(ans.begin()+x+1, ans.begin()+y+1); } if (!ok || __builtin_popcount(ans[0] ^ ans.back()) != k) continue; else { cout << (1 << n) << "\n"; for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if ((ans[i] >> (n-j-1)) & 1) ss[j] = '1'; else ss[j] = '0'; } cout << ss << "\n"; } } return 0; } cout << "-1\n"; } else if (k == 1) { vector<int> ans((1 << n), -1); vector<bool> vis((1 << n), 0); ans[0] = 0; vis[0] = 1; bool ok = 1; for (int i = 1; i < (1 << n); i++) { int x = ans[i-1]; for (int j = 0; j < n; j++) { if (vis[x ^ (1 << j)]) continue; ans[i] = x ^ (1 << j); vis[x ^ (1 << j)] = 1; break; } if (ans[i] == -1) ok = 0; } if (!ok) { cout << "-1\n"; return 0; } cout << (1 << n) << "\n"; for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if ((ans[i] >> (n-j-1)) & 1) ss[j] = '1'; else ss[j] = '0'; } cout << ss << "\n"; } } else if (k == 3) { vector<int> ans((1 << n), -1); vector<bool> vis((1 << n), 0); ans[0] = 0; vis[0] = 1; bool ok = 1; for (int i = 1; i < (1 << n); i++) { int x = ans[i-1]; for (int j = 0; j < n && ans[i] == -1; j++) { for (int j2 = j+1; j2 < n && ans[i] == -1; j2++) { for (int j3 = j2+1; j3 < n; j3++) { if (vis[x ^ (1 << j) ^ (1 << j2) ^ (1 << j3)]) continue; ans[i] = x ^ (1 << j) ^ (1 << j2) ^ (1 << j3); vis[x ^ (1 << j) ^ (1 << j2) ^ (1 << j3)] = 1; break; } } } if (ans[i] == -1) ok = 0; } if (!ok) { cout << "-1\n"; return 0; } cout << (1 << n) << "\n"; for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if ((ans[i] >> (n-j-1)) & 1) ss[j] = '1'; else ss[j] = '0'; } cout << ss << "\n"; } } else { vector<int> almacenDeVideosParaAdultosDeEsomer; for (int i = 0; i < (1 << n); i++) { if (i != s && __builtin_popcount(i) == k) { almacenDeVideosParaAdultosDeEsomer.push_back(i); } } shuffle(all(almacenDeVideosParaAdultosDeEsomer), rng); int sz = almacenDeVideosParaAdultosDeEsomer.size(); vector<int> ans((1 << n), -1); vector<bool> vis((1 << n), 0); //cerr << s << endl; ans[0] = s; vis[s] = 1; bool ok = 1; for (int i = 1; i < (1 << n); i++) { int x = ans[i-1]; while (1) { int j2 = rng() % sz; int y = almacenDeVideosParaAdultosDeEsomer[j2]; //cerr << x << " " << y << " " << (x ^ y) << endl; if (vis[x ^ y]) continue; ans[i] = x ^ y; vis[x ^ y] = 1; break; } if (ans[i] == -1) { ok = 0; break; } } if (!ok) { cout << "-1\n"; return 0; } cout << (1 << n) << "\n"; for (int i = 0; i < (1 << n); i++) { for (int j = 0; j < n; j++) { if ((ans[i] >> (n-j-1)) & 1) ss[j] = '1'; else ss[j] = '0'; } cout << ss << "\n"; } } }

Compilation message (stderr)

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:25:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |   while (ss.size() < n) ss = "0"+ss;
      |          ~~~~~~~~~~^~~
#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...