Submission #503164

#	Time	Username	Problem	Language	Result	Execution time	Memory
503164		stanislavpolyn	"The Lyuboyn" code (IZhO19_lyuboyn)	C++17	100 / 100	230 ms	23320 KiB

lyuboyn

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

#define fr(i, a, b) for(int i = (a); i <= (b); ++i)
#define rf(i, a, b) for(int i = (a); i >= (b); --i)
#define fe(x, y) for(auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template<typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template<typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T>
using ve = vector<T>;

int n, k, t;
string s;

ve<int> ans;
ve<int> go;
bool vis[pw(18)];

int func(int a, int b) {
    return __builtin_popcount(a ^ b);
}

int first;

void rec() {
    if(sz(ans) == pw(n)) {
        cout << sz(ans) << "\n";

//        fr(i, 1, sz(ans) - 1) {
//            assert(func(ans[i], ans[i - 1]) == k);
//        }

        assert(ans[0] == first);
        fe(x, ans) {
            fr(j, 0, n - 1) {
                cout << !!(x & pw(j));
            }
            cout << "\n";
        }
        exit(0);
    }

    fe(cur, go) {
        int mask = ans.back() ^ cur;
//        assert(func(mask, ans.back()) == k);

        if(!vis[mask]) {
            vis[mask] = 1;
            ans.pb(mask);
            rec();
            ans.pop_back();
            vis[mask] = 0;
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> k >> t;

    if(k % 2 == 0) {
        cout << "-1\n";
        return 0;
    }

    cin >> s;

    if(k == 1 && s == "0") {
        cout << pw(n) << "\n";
        fr(i, 0, pw(n) - 1) {
            int mask = i ^ (i >> 1);
            fr(j, 0, n - 1) {
                cout << !!(mask & pw(j));
            }
            cout << "\n";
        }

        return 0;
    }

    fr(mask, 0, pw(n) - 1) {
        if(__builtin_popcount(mask) == k) {
            go.pb(mask);
        }
    }



    int mask = 0;
    rf(i, sz(s) - 1, 0) {
        mask = mask * 2 + (s[i] - '0');
    }
    first = mask;
    vis[mask] = 1;
    ans.pb(mask);
    rec();

//    cout << "-1\n";
//    cin >> s;



//    sort(all(ans));
//    ans.erase(unique(all(ans)), ans.end());
//    assert(sz(ans) == pw(n) - 1);

    return 0;
}

• 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