oj.uz

Submission #503164

# Submission time Handle Problem Language Result Execution time Memory
503164 2022-01-07T12:05:21 Z stanislavpolyn "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 230 ms 23320 KB 
#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 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Ok
2 Correct 0 ms 328 KB Ok
3 Correct 0 ms 204 KB Ok
4 Correct 0 ms 324 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 324 KB Ok
7 Correct 1 ms 300 KB Ok
8 Correct 0 ms 204 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23092 KB Ok
2 Correct 101 ms 11752 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Ok
2 Correct 5 ms 1004 KB Ok
3 Correct 102 ms 11628 KB Ok
4 Correct 54 ms 5940 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 2 ms 460 KB Ok
7 Correct 25 ms 3172 KB Ok
8 Correct 1 ms 324 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 23248 KB Ok
2 Correct 215 ms 23072 KB Ok
3 Correct 212 ms 23088 KB Ok
4 Correct 97 ms 11712 KB Ok
5 Correct 111 ms 11580 KB Ok
6 Correct 68 ms 5988 KB Ok
7 Correct 48 ms 5972 KB Ok
8 Correct 24 ms 3124 KB Ok
9 Correct 22 ms 3128 KB Ok
10 Correct 15 ms 1636 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 312 KB Ok
13 Correct 1 ms 332 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23092 KB Ok
2 Correct 101 ms 11752 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 1 ms 332 KB Ok
7 Correct 5 ms 1004 KB Ok
8 Correct 102 ms 11628 KB Ok
9 Correct 54 ms 5940 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 2 ms 460 KB Ok
12 Correct 25 ms 3172 KB Ok
13 Correct 1 ms 324 KB Ok
14 Correct 203 ms 23248 KB Ok
15 Correct 215 ms 23072 KB Ok
16 Correct 212 ms 23088 KB Ok
17 Correct 97 ms 11712 KB Ok
18 Correct 111 ms 11580 KB Ok
19 Correct 68 ms 5988 KB Ok
20 Correct 48 ms 5972 KB Ok
21 Correct 24 ms 3124 KB Ok
22 Correct 22 ms 3128 KB Ok
23 Correct 15 ms 1636 KB Ok
24 Correct 1 ms 320 KB Ok
25 Correct 1 ms 312 KB Ok
26 Correct 1 ms 332 KB Ok
27 Correct 207 ms 23100 KB Ok
28 Correct 109 ms 11688 KB Ok
29 Correct 206 ms 23320 KB Ok
30 Correct 11 ms 1700 KB Ok
31 Correct 1 ms 332 KB Ok
32 Correct 6 ms 972 KB Ok
33 Correct 22 ms 3124 KB Ok
34 Correct 0 ms 332 KB Ok
35 Correct 1 ms 324 KB Ok
36 Correct 1 ms 332 KB Ok
37 Correct 1 ms 324 KB Ok
38 Correct 100 ms 11668 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 11684 KB Ok
2 Correct 220 ms 23056 KB Ok
3 Correct 216 ms 23268 KB Ok
4 Correct 11 ms 1732 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 24 ms 3120 KB Ok
7 Correct 230 ms 23092 KB Ok
8 Correct 1 ms 316 KB Ok
9 Correct 0 ms 204 KB Ok
10 Correct 1 ms 320 KB Ok
11 Correct 47 ms 5972 KB Ok
12 Correct 108 ms 11680 KB Ok