Submission #378380

#	Time	Username	Problem	Language	Result	Execution time	Memory
378380		abc864197532	"The Lyuboyn" code (IZhO19_lyuboyn)	C++17	100 / 100	841 ms	6616 KiB

lyuboyn

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 200000, logN = 18, K = 333;

vector <int> gray_code(int n) {
    if (n == 1) return {0, 1};
    vector <int> under = gray_code(n - 1);
    vector <int> ans;
    for (int i : under) ans.pb(i);
    reverse(all(under));
    for (int i : under) ans.pb(i | (1 << n - 1));
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, t;
    string str;
    cin >> n >> k >> t >> str;
    int from = 0;
    for (int i = 0; i < n; ++i) from = (from << 1) | (str[i] == '1');
    if (k & 1 ^ 1) {
        cout << -1 << endl;
        return 0;
    }
    auto output = [&](int v) {
        v ^= from;
        for (int i = n - 1; ~i; --i) cout << (v >> i & 1);
        cout << endl;
    };
    cout << (1 << n) << endl;
    if (k == 1) {
        vector <int> ans = gray_code(n);
        for (int i : ans) output(i);
        return 0;
    }
    k >>= 1;
    vector <int> right = gray_code(k * 2);
    vector <int> lefta = gray_code(n - k * 2), leftb = lefta;
    for (int i = 0; i < leftb.size(); ++i) {
        leftb[i] ^= (1 << n - k * 2 - 2);
    }
    for (int i = 0; i < right.size(); ++i) {
        if (i & 1 ^ 1) {
            for (int j = 0; j < lefta.size(); ++j) {
                output(lefta[j] << (k * 2) | right[i]);
                right[i] ^= ((1 << k * 2) - 1);
            }
        } else {
            for (int j = 0; j < leftb.size(); ++j) {
                output(leftb[j] << (k * 2) | right[i]);
                right[i] ^= ((1 << k * 2) - 1);
            }
        }
    }
}

Compilation message (stderr)

lyuboyn.cpp: In function 'std::vector<int> gray_code(int)':
lyuboyn.cpp:34:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |     for (int i : under) ans.pb(i | (1 << n - 1));
      |                                          ~~^~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:46:11: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   46 |     if (k & 1 ^ 1) {
      |         ~~^~~
lyuboyn.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < leftb.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
lyuboyn.cpp:65:37: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   65 |         leftb[i] ^= (1 << n - k * 2 - 2);
      |                           ~~~~~~~~~~^~~
lyuboyn.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < right.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
lyuboyn.cpp:68:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   68 |         if (i & 1 ^ 1) {
      |             ~~^~~
lyuboyn.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j = 0; j < lefta.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~
lyuboyn.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int j = 0; j < leftb.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 31 / 31
• Subtask 8: 17 / 17