oj.uz

답안 #998639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998639 2024-06-14T11:58:15 Z GrindMachine "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 96 ms 45552 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Ok

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 0 ms 348 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 348 KB Ok
7 Correct 0 ms 348 KB Ok
8 Correct 0 ms 348 KB Ok

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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