Submission #315655

#	Time	Username	Problem	Language	Result	Execution time	Memory
315655		farmerboy	"The Lyuboyn" code (IZhO19_lyuboyn)	C++14	100 / 100	264 ms	5496 KiB

lyuboyn

/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

const int D = 19;
int basis[D];
vector<int> a;

void insertVector(int mask) {
    int originalMask = mask;
    FOR(i,0,D-1) {
        if (!(mask & (1<<i))) continue;
        if (!basis[i]) {
            basis[i] = mask;
            a.push_back(originalMask);
            return;
        }
        mask ^= basis[i];
    }
}

int gray(int n) {
    return n ^ (n >> 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    int n, k, t;
    cin >> n >> k >> t;
    string s;
    cin >> s;
    int fi = 0;
    FOR(i,0,SZ(s)-1) fi = fi * 2 + s[i] - '0';
    FOR(j,1,(1<<n)-1)
        if (__builtin_popcount(j) == k) insertVector(j);
    if (SZ(a) < n) {
        cout << "-1";
        return 0;
    }
    cout << (1<<n) << '\n';
    FOR(i,0,(1<<n)-1) {
        int x = gray(i);
        int res = fi;
        FOR(j,0,n-1)
            if (x & (1<<j)) res ^= a[j];
        FORE(j,n-1,0) cout << (res >> j & 1);
        cout << "\n";
    }
    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