oj.uz

Submission #315652

# Submission time Handle Problem Language Result Execution time Memory
315652 2020-10-23T14:31:21 Z farmerboy "The Lyuboyn" code (IZhO19_lyuboyn) C++14
14 / 100
 236 ms 5496 KB 
/*
    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) ^ fi;
        int res = 0;
        FOR(j,0,n-1)
            if (x & (1<<j)) res ^= a[j];
        FORE(j,n-1,0) cout << (x >> j & 1);
        cout << "\n";
    }
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Ok

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Fail, not exactly k bits are different: line = 0

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Ok
2 Correct 1 ms 384 KB Ok
3 Correct 3 ms 384 KB Ok
4 Correct 1 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 1 ms 384 KB Ok
8 Correct 2 ms 384 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 5496 KB Ok
2 Correct 110 ms 2680 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Fail, not exactly k bits are different: line = 0
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 5496 KB Fail, not exactly k bits are different: line = 0
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 5496 KB Ok
2 Correct 110 ms 2680 KB Ok
3 Correct 1 ms 384 KB Ok
4 Correct 0 ms 384 KB Ok
5 Correct 1 ms 384 KB Ok
6 Incorrect 1 ms 384 KB Fail, not exactly k bits are different: line = 0
7 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 2680 KB Fail, not exactly k bits are different: line = 0
2 Halted 0 ms 0 KB -