oj.uz

Submission #1094806

# Submission time Handle Problem Language Result Execution time Memory
1094806 2024-09-30T15:36:59 Z makrav "The Lyuboyn" code (IZhO19_lyuboyn) C++14
8 / 100
 28 ms 7080 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

int count(int x, int y) {
    return __builtin_popcount((x ^ y));
}

string int2s(int x, int siz) {
    string rs;
    while (x) {
        rs += char('0' + (x & 1));
        x >>= 1;
    }
    while (sz(rs) < siz) rs += '0';
    return rs;
}

void solve() {
    int n, k, t; cin >> n >> k >> t;
    string S; cin >> S;
    if (k % 2 == 0) {
        cout << "-1\n";
        return;
    }

    auto solve2 = [&](int N, auto&&self) -> vector<int> {
        if (N == 2) return {3};
        if (N == 3) return {6, 3, 6};

        auto ans = self(N - 2, self);
        int X = 0;
        for (int i = 0; i < sz(ans); i++) X = (X ^ ans[i]);
        int start2 = 0;
        for (int val = 0; val < (1 << (N - 2)); val++) {
            if (count(0, val) == 1 && count(X, val) == 1) start2 = val;
        }
        assert(start2);
        vector<int> newans;
        vector<int> lol = {0, 2, 3, 1};
        for (int i = 0; i < 4; i++) {
            for (int u : ans) newans.pb(u);
            if (i < 3) {
                newans.pb((start2^X)+(lol[i+1]^lol[i])*(1<<(N-2)));
            }
        }
        return newans;
    };
    vector<int> rs = solve2(n, solve2);
    int XR = 0;
    for (auto &u : rs) XR ^= u;
    rs.pb(XR);
    vector<int> ans;
    for (int i = 0; i < (1 << n); i++) {
        if (count(i, 0) == k && count(i, rs[0]) == k) {
            int cur1 = 0, cur2 = i;
            for (int j = 0; j < (1 << n); j++) {
                if (j % 2 == 0) {
                    ans.pb(cur1);
                    cur1 ^= rs[j >> 1];
                } else {
                    ans.pb(cur2);
                    cur2 ^= rs[((j >> 1) + 1) % sz(rs)];
                }
            }
            break;
        }
    }
    cout << sz(ans) << '\n';
    for (int i = 0; i < sz(ans); i++) {
        if (int2s(ans[i], n) == S) {
            int cur = i, cnt = sz(ans);
            while (cnt) {
                cout << int2s(ans[cur], n) << '\n';
                cur = cur + 1;
                if (cur >= sz(ans)) cur = 0;
                cnt--;
            }
            return;
        }
    }
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 31.0

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

Subtask #8
0 / 17.0

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