oj.uz

Submission #315655

# Submission time Handle Problem Language Result Execution time Memory
315655 2020-10-23T14:39:40 Z farmerboy "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 264 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);
        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 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 5368 KB Ok
2 Correct 116 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Ok
2 Correct 6 ms 512 KB Ok
3 Correct 118 ms 2680 KB Ok
4 Correct 56 ms 1400 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 2 ms 384 KB Ok
7 Correct 27 ms 888 KB Ok
8 Correct 1 ms 384 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 5368 KB Ok
2 Correct 258 ms 5496 KB Ok
3 Correct 254 ms 5496 KB Ok
4 Correct 122 ms 2680 KB Ok
5 Correct 118 ms 2808 KB Ok
6 Correct 56 ms 1400 KB Ok
7 Correct 56 ms 1400 KB Ok
8 Correct 27 ms 888 KB Ok
9 Correct 28 ms 1016 KB Ok
10 Correct 13 ms 640 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 ms 384 KB Ok
13 Correct 1 ms 384 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 5368 KB Ok
2 Correct 116 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 Correct 1 ms 288 KB Ok
7 Correct 6 ms 512 KB Ok
8 Correct 118 ms 2680 KB Ok
9 Correct 56 ms 1400 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 2 ms 384 KB Ok
12 Correct 27 ms 888 KB Ok
13 Correct 1 ms 384 KB Ok
14 Correct 255 ms 5368 KB Ok
15 Correct 258 ms 5496 KB Ok
16 Correct 254 ms 5496 KB Ok
17 Correct 122 ms 2680 KB Ok
18 Correct 118 ms 2808 KB Ok
19 Correct 56 ms 1400 KB Ok
20 Correct 56 ms 1400 KB Ok
21 Correct 27 ms 888 KB Ok
22 Correct 28 ms 1016 KB Ok
23 Correct 13 ms 640 KB Ok
24 Correct 1 ms 384 KB Ok
25 Correct 1 ms 384 KB Ok
26 Correct 1 ms 384 KB Ok
27 Correct 249 ms 5368 KB Ok
28 Correct 119 ms 2684 KB Ok
29 Correct 259 ms 5368 KB Ok
30 Correct 13 ms 640 KB Ok
31 Correct 1 ms 384 KB Ok
32 Correct 7 ms 512 KB Ok
33 Correct 27 ms 888 KB Ok
34 Correct 1 ms 384 KB Ok
35 Correct 0 ms 384 KB Ok
36 Correct 1 ms 384 KB Ok
37 Correct 0 ms 384 KB Ok
38 Correct 123 ms 2684 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2680 KB Ok
2 Correct 253 ms 5368 KB Ok
3 Correct 252 ms 5368 KB Ok
4 Correct 13 ms 640 KB Ok
5 Correct 1 ms 384 KB Ok
6 Correct 28 ms 888 KB Ok
7 Correct 264 ms 5368 KB Ok
8 Correct 1 ms 384 KB Ok
9 Correct 1 ms 384 KB Ok
10 Correct 1 ms 384 KB Ok
11 Correct 58 ms 1400 KB Ok
12 Correct 123 ms 2680 KB Ok