oj.uz

Submission #583672

# Submission time Handle Problem Language Result Execution time Memory
583672 2022-06-26T02:58:17 Z KoD "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 230 ms 6528 KB 
#include <bits/stdc++.h>

using ll = long long;
using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    vector<int> base, use;
    int N, K, T;
    std::string S;
    std::cin >> N >> K >> T >> S;
    const int first = std::stoi(S, 0, 2);
    for (int i = 0; i < (1 << N); ++i) {
        if (__builtin_popcount(i) == K) {
            int x = i;
            for (const int e : base) {
                x = std::min(x, x ^ e);
            }
            if (x != 0) {
                base.push_back(x);
                use.push_back(i);
            }
        } 
    }
    if ((int)base.size() != N) {
        std::cout << "-1\n";
        return 0;
    }
    auto dfs = [&](auto&& dfs, const int n) -> vector<int> {
        if (n == 0) {
            return {0};
        }
        auto low = dfs(dfs, n - 1);
        vector<int> ret(1 << n);
        const int m = 1 << (n - 1);
        for (int i = 0; i < m; ++i) {
            ret[i] = low[i];
            ret[2 * m - i - 1] = low[i] + m;
        }
        return ret;
    };
    const auto code = dfs(dfs, N);
    std::cout << (1 << N) << '\n';
    for (int i = 0; i < (1 << N); ++i) {
        int x = first;
        for (int j = 0; j < N; ++j) {
            if (code[i] >> j & 1) {
                x ^= use[j];
            }
        }
        for (int j = N - 1; j >= 0; --j) {
            std::cout << (x >> j & 1);
        }
        std::cout << '\n';
    }
    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 6528 KB Ok
2 Correct 101 ms 3320 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 5 ms 468 KB Ok
3 Correct 97 ms 3236 KB Ok
4 Correct 55 ms 1816 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 2 ms 340 KB Ok
7 Correct 24 ms 1040 KB Ok
8 Correct 1 ms 212 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 6428 KB Ok
2 Correct 226 ms 6496 KB Ok
3 Correct 217 ms 6468 KB Ok
4 Correct 101 ms 3220 KB Ok
5 Correct 104 ms 3260 KB Ok
6 Correct 46 ms 1768 KB Ok
7 Correct 46 ms 1820 KB Ok
8 Correct 22 ms 976 KB Ok
9 Correct 27 ms 968 KB Ok
10 Correct 11 ms 576 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 212 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 6528 KB Ok
2 Correct 101 ms 3320 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 0 ms 212 KB Ok
7 Correct 5 ms 468 KB Ok
8 Correct 97 ms 3236 KB Ok
9 Correct 55 ms 1816 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 2 ms 340 KB Ok
12 Correct 24 ms 1040 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 205 ms 6428 KB Ok
15 Correct 226 ms 6496 KB Ok
16 Correct 217 ms 6468 KB Ok
17 Correct 101 ms 3220 KB Ok
18 Correct 104 ms 3260 KB Ok
19 Correct 46 ms 1768 KB Ok
20 Correct 46 ms 1820 KB Ok
21 Correct 22 ms 976 KB Ok
22 Correct 27 ms 968 KB Ok
23 Correct 11 ms 576 KB Ok
24 Correct 1 ms 320 KB Ok
25 Correct 1 ms 340 KB Ok
26 Correct 1 ms 212 KB Ok
27 Correct 213 ms 6356 KB Ok
28 Correct 102 ms 3336 KB Ok
29 Correct 211 ms 6440 KB Ok
30 Correct 10 ms 596 KB Ok
31 Correct 1 ms 340 KB Ok
32 Correct 5 ms 484 KB Ok
33 Correct 22 ms 1052 KB Ok
34 Correct 1 ms 212 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 1 ms 324 KB Ok
37 Correct 1 ms 212 KB Ok
38 Correct 97 ms 3216 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3248 KB Ok
2 Correct 206 ms 6388 KB Ok
3 Correct 210 ms 6404 KB Ok
4 Correct 11 ms 596 KB Ok
5 Correct 1 ms 320 KB Ok
6 Correct 31 ms 1004 KB Ok
7 Correct 204 ms 6368 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 47 ms 1768 KB Ok
12 Correct 102 ms 3312 KB Ok