oj.uz

Submission #503162

# Submission time Handle Problem Language Result Execution time Memory
503162 2022-01-07T12:01:43 Z stanislavpolyn "The Lyuboyn" code (IZhO19_lyuboyn) C++17
34 / 100
 261 ms 23228 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";

        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;
    fr(i, 0, sz(s) - 1) {
        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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB First number in answer is not x 1 2

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 23224 KB Ok
2 Correct 104 ms 11568 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Ok
2 Correct 6 ms 972 KB Ok
3 Correct 120 ms 11564 KB Ok
4 Correct 49 ms 5956 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 1 ms 472 KB Ok
7 Correct 26 ms 3164 KB Ok
8 Correct 0 ms 332 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 23228 KB First number in answer is not x 44202 87252
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 23224 KB Ok
2 Correct 104 ms 11568 KB Ok
3 Correct 1 ms 332 KB Ok
4 Correct 0 ms 204 KB Ok
5 Correct 0 ms 204 KB Ok
6 Correct 0 ms 204 KB Ok
7 Correct 6 ms 972 KB Ok
8 Correct 120 ms 11564 KB Ok
9 Correct 49 ms 5956 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 1 ms 472 KB Ok
12 Correct 26 ms 3164 KB Ok
13 Correct 0 ms 332 KB Ok
14 Incorrect 226 ms 23228 KB First number in answer is not x 44202 87252
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 11620 KB First number in answer is not x 92826 45741
2 Halted 0 ms 0 KB -