Submission #998639

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998639	2024-06-14T11:58:15 Z	GrindMachine	"The Lyuboyn" code (IZhO19_lyuboyn)	C++17	100 / 100	96 ms	45552 KB

lyuboyn

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k,t; cin >> n >> k >> t;
    string s; cin >> s;

    if(!(k&1)){
        cout << -1 << endl;
        return;
    }

    auto f = [&](string s1, string s2){
        ll diff = 0;
        rep(i,sz(s1)){
            diff += s1[i]!=s2[i];
        }
        return diff;
    };

    // gray code for n = k+1 bits
    vector<string> ans = {"00","01","11","10"};
    for(int i = 3; i <= k+1; ++i){
        auto ans2 = ans;
        trav(t,ans2) t = "0"+t;
        reverse(all(ans));
        trav(t,ans) ans2.pb("1"+t);
        ans = ans2;
    }

    // permutation of n = k+1 bits s.t adj values are same in only 1 bit
    rep(i,sz(ans)){
        if(i&1){
            trav(x,ans[i]){
                if(x == '1') x = '0';
                else x = '1';
            }
        }
    }

    for(int i = k+2; i <= n; ++i){
        if(k == 1){
            auto ans2 = ans;
            trav(t,ans2) t = "0"+t;
            reverse(all(ans));
            trav(t,ans) ans2.pb("1"+t);
            ans = ans2;
            conts;
        }

        auto ans2 = ans;
        trav(t,ans2) t = "0"+t;
        ll ind = -1;
        rep1(j,sz(ans)-1){
            if(f(ans[j],ans.back()) == k-1 and f(ans[j-1],ans[0]) == k-1){
                ind = j;
                break;
            }
        }

        assert(ind != -1);
        ll times = 0;

        for(int i = ind; ; i = (i+1)%sz(ans)){
            if(i == ind) times++;
            if(times == 2) break;
            auto t = ans[i];
            t = "1"+t;
            ans2.pb(t);
        }

        ans = ans2;
        assert(f(ans[0],ans.back()) == k);
    }
    
    ll pos = find(all(ans),s)-ans.begin();
    rotate(ans.begin(),ans.begin()+pos,ans.end());

    rep(i,sz(ans)){
        assert(f(ans[i],ans[(i+1)%sz(ans)]) == k);
    }

    cout << (1<<n) << endl;
    trav(x,ans) cout << x << endl;

    /*

    ll n = 8, k = 2;
    vector<ll> a(n);
    iota(all(a),0);

    do{

        bool ok = true;
        rep(i,n-1){
            ll xo = a[i]^a[i+1];
            if(setbits(xo) != k){
                ok = false;
                break;
            }
        }

        if(ok){
            debug(a);
        }

    } while(next_permutation(all(a)));

    */
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Ok
2	Correct	348 KB	Ok
3	Correct	348 KB	Ok
4	Correct	348 KB	Ok
5	Correct	348 KB	Ok
6	Correct	348 KB	Ok
7	Correct	348 KB	Ok
8	Correct	348 KB	Ok

Subtask #4
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	45448 KB	Ok
2	Correct	39 ms	22940 KB	Ok
3	Correct	0 ms	348 KB	Ok
4	Correct	0 ms	348 KB	Ok
5	Correct	0 ms	348 KB	Ok

Subtask #5
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Ok
2	Correct	2 ms	1240 KB	Ok
3	Correct	41 ms	21972 KB	Ok
4	Correct	20 ms	10176 KB	Ok
5	Correct	0 ms	344 KB	Ok
6	Correct	1 ms	604 KB	Ok
7	Correct	6 ms	3532 KB	Ok
8	Correct	0 ms	348 KB	Ok

Subtask #6
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	43464 KB	Ok
2	Correct	87 ms	43412 KB	Ok
3	Correct	84 ms	43392 KB	Ok
4	Correct	43 ms	21976 KB	Ok
5	Correct	43 ms	21948 KB	Ok
6	Correct	18 ms	10176 KB	Ok
7	Correct	16 ms	10692 KB	Ok
8	Correct	6 ms	3528 KB	Ok
9	Correct	6 ms	3532 KB	Ok
10	Correct	3 ms	2004 KB	Ok
11	Correct	0 ms	452 KB	Ok
12	Correct	1 ms	348 KB	Ok
13	Correct	0 ms	456 KB	Ok

Subtask #7
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	45448 KB	Ok
2	Correct	39 ms	22940 KB	Ok
3	Correct	0 ms	348 KB	Ok
4	Correct	0 ms	348 KB	Ok
5	Correct	0 ms	348 KB	Ok
6	Correct	0 ms	344 KB	Ok
7	Correct	2 ms	1240 KB	Ok
8	Correct	41 ms	21972 KB	Ok
9	Correct	20 ms	10176 KB	Ok
10	Correct	0 ms	344 KB	Ok
11	Correct	1 ms	604 KB	Ok
12	Correct	6 ms	3532 KB	Ok
13	Correct	0 ms	348 KB	Ok
14	Correct	87 ms	43464 KB	Ok
15	Correct	87 ms	43412 KB	Ok
16	Correct	84 ms	43392 KB	Ok
17	Correct	43 ms	21976 KB	Ok
18	Correct	43 ms	21948 KB	Ok
19	Correct	18 ms	10176 KB	Ok
20	Correct	16 ms	10692 KB	Ok
21	Correct	6 ms	3528 KB	Ok
22	Correct	6 ms	3532 KB	Ok
23	Correct	3 ms	2004 KB	Ok
24	Correct	0 ms	452 KB	Ok
25	Correct	1 ms	348 KB	Ok
26	Correct	0 ms	456 KB	Ok
27	Correct	84 ms	45552 KB	Ok
28	Correct	39 ms	21968 KB	Ok
29	Correct	92 ms	43392 KB	Ok
30	Correct	3 ms	2000 KB	Ok
31	Correct	1 ms	348 KB	Ok
32	Correct	2 ms	1240 KB	Ok
33	Correct	11 ms	3532 KB	Ok
34	Correct	1 ms	344 KB	Ok
35	Correct	1 ms	348 KB	Ok
36	Correct	0 ms	348 KB	Ok
37	Correct	0 ms	348 KB	Ok
38	Correct	39 ms	21804 KB	Ok

Subtask #8
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	21924 KB	Ok
2	Correct	81 ms	45464 KB	Ok
3	Correct	89 ms	43364 KB	Ok
4	Correct	5 ms	2004 KB	Ok
5	Correct	0 ms	348 KB	Ok
6	Correct	6 ms	3532 KB	Ok
7	Correct	96 ms	43444 KB	Ok
8	Correct	1 ms	348 KB	Ok
9	Correct	0 ms	348 KB	Ok
10	Correct	1 ms	348 KB	Ok
11	Correct	28 ms	10692 KB	Ok
12	Correct	42 ms	21944 KB	Ok

Submission #998639

Compilation message