Submission #998642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998642	2024-06-14T12:01:44 Z	GrindMachine	"The Lyuboyn" code (IZhO19_lyuboyn)	C++17	100 / 100	101 ms	45572 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
    // flip the values of the gray code that are at odd positions
    rep(i,sz(ans)){
        if(i&1){
            trav(x,ans[i]){
                if(x == '1') x = '0';
                else x = '1';
            }
        }
    }

    // solution for n = k+1 already known
    // inductively build for n+1 (add 1 more bit to the beginning)
    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	0 ms	344 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	344 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	80 ms	45572 KB	Ok
2	Correct	37 ms	22968 KB	Ok
3	Correct	1 ms	344 KB	Ok
4	Correct	0 ms	344 KB	Ok
5	Correct	1 ms	348 KB	Ok

Subtask #5
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Ok
2	Correct	2 ms	1240 KB	Ok
3	Correct	39 ms	21824 KB	Ok
4	Correct	17 ms	10176 KB	Ok
5	Correct	0 ms	348 KB	Ok
6	Correct	1 ms	604 KB	Ok
7	Correct	6 ms	3532 KB	Ok
8	Correct	1 ms	348 KB	Ok

Subtask #6
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	43536 KB	Ok
2	Correct	90 ms	43324 KB	Ok
3	Correct	84 ms	43404 KB	Ok
4	Correct	41 ms	21948 KB	Ok
5	Correct	41 ms	21948 KB	Ok
6	Correct	18 ms	10180 KB	Ok
7	Correct	16 ms	10692 KB	Ok
8	Correct	6 ms	3532 KB	Ok
9	Correct	6 ms	3532 KB	Ok
10	Correct	3 ms	2004 KB	Ok
11	Correct	0 ms	348 KB	Ok
12	Correct	1 ms	348 KB	Ok
13	Correct	1 ms	348 KB	Ok

Subtask #7
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	45572 KB	Ok
2	Correct	37 ms	22968 KB	Ok
3	Correct	1 ms	344 KB	Ok
4	Correct	0 ms	344 KB	Ok
5	Correct	1 ms	348 KB	Ok
6	Correct	0 ms	348 KB	Ok
7	Correct	2 ms	1240 KB	Ok
8	Correct	39 ms	21824 KB	Ok
9	Correct	17 ms	10176 KB	Ok
10	Correct	0 ms	348 KB	Ok
11	Correct	1 ms	604 KB	Ok
12	Correct	6 ms	3532 KB	Ok
13	Correct	1 ms	348 KB	Ok
14	Correct	88 ms	43536 KB	Ok
15	Correct	90 ms	43324 KB	Ok
16	Correct	84 ms	43404 KB	Ok
17	Correct	41 ms	21948 KB	Ok
18	Correct	41 ms	21948 KB	Ok
19	Correct	18 ms	10180 KB	Ok
20	Correct	16 ms	10692 KB	Ok
21	Correct	6 ms	3532 KB	Ok
22	Correct	6 ms	3532 KB	Ok
23	Correct	3 ms	2004 KB	Ok
24	Correct	0 ms	348 KB	Ok
25	Correct	1 ms	348 KB	Ok
26	Correct	1 ms	348 KB	Ok
27	Correct	101 ms	45448 KB	Ok
28	Correct	40 ms	21924 KB	Ok
29	Correct	86 ms	43408 KB	Ok
30	Correct	3 ms	2000 KB	Ok
31	Correct	0 ms	348 KB	Ok
32	Correct	2 ms	1236 KB	Ok
33	Correct	6 ms	3532 KB	Ok
34	Correct	0 ms	348 KB	Ok
35	Correct	0 ms	348 KB	Ok
36	Correct	0 ms	348 KB	Ok
37	Correct	0 ms	348 KB	Ok
38	Correct	41 ms	21884 KB	Ok

Subtask #8
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	21928 KB	Ok
2	Correct	82 ms	45528 KB	Ok
3	Correct	84 ms	43400 KB	Ok
4	Correct	3 ms	2000 KB	Ok
5	Correct	0 ms	348 KB	Ok
6	Correct	6 ms	3532 KB	Ok
7	Correct	85 ms	43512 KB	Ok
8	Correct	0 ms	348 KB	Ok
9	Correct	0 ms	348 KB	Ok
10	Correct	0 ms	348 KB	Ok
11	Correct	16 ms	10728 KB	Ok
12	Correct	40 ms	21948 KB	Ok

Submission #998642

Compilation message