oj.uz

Submission #151298

# Submission time Handle Problem Language Result Execution time Memory
151298 2019-09-02T12:02:33 Z andrew "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 996 ms 38956 KB 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

ll Val(string s){
    ll ans = 0;
    for(auto i : s){
        ans *= 2;
        ans |= i - '0';
    }
    return ans;
}

ll n;

string Fst(ll x){
    string ans;

    for(int i = n - 1; i >= 0; i--){
        if((x & pw(i))){
            ans += "1";
        }else ans += "0";
    }
    return ans;
}

ll kol(ll a, ll b){
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if((a & pw(i)) != (b & pw(i)))ans++;
    }
    return ans;
}

bool f[MAXN];
ll t, k;
vector <ll> a, c;

void dfs(ll x){
    if(clock() / (double)CLOCKS_PER_SEC > 0.995)vout(-1);
    f[x] = 1;
    a.p_b(x);
    if(a.size() == pw(n)){
        if(t == 0 || (t == 1 && kol(a.back(), a[0]) == k)){
            cout << a.size() << "\n";
            for(auto i : a)cout << Fst(i) << "\n";
            exit(0);
        }
        a.pop_back();
    }else{
        for(auto i : c){
            if(f[x ^ i])continue;
            dfs(x ^ i);
            if(rnd() % 63 == 17)break;
        }
    }
    a.pop_back();
    f[x] = 0;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> t;
    vector <ll> a(pw(n));
    for(int i = 0; i < pw(n); i++)a[i] = i;
    string st;
    cin >> st;
    ll s = Val(st);
    for(int i = 0; i < pw(n); i++)if(__builtin_popcount(i) == k)c.p_b(i);

    shuffle(all(c), rnd);

    dfs(s);

    vout(-1);

    return 0;
}

Compilation message

lyuboyn.cpp: In function 'void dfs(ll)':
lyuboyn.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a.size() == pw(n)){
                 ^

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 995 ms 976 KB Ok
2 Correct 996 ms 18288 KB Ok
3 Correct 996 ms 9692 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 995 ms 424 KB Ok
6 Correct 995 ms 504 KB Ok
7 Correct 995 ms 1016 KB Ok
8 Correct 995 ms 9476 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 38632 KB Ok
2 Correct 185 ms 19392 KB Ok
3 Correct 3 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 380 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 13 ms 1528 KB Ok
3 Correct 189 ms 19396 KB Ok
4 Correct 97 ms 9916 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 5 ms 680 KB Ok
7 Correct 47 ms 5116 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 38956 KB Ok
2 Correct 394 ms 38632 KB Ok
3 Correct 377 ms 38632 KB Ok
4 Correct 196 ms 19564 KB Ok
5 Correct 192 ms 19476 KB Ok
6 Correct 101 ms 9908 KB Ok
7 Correct 92 ms 9864 KB Ok
8 Correct 47 ms 5116 KB Ok
9 Correct 48 ms 5236 KB Ok
10 Correct 25 ms 2808 KB Ok
11 Correct 3 ms 504 KB Ok
12 Correct 3 ms 504 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 38632 KB Ok
2 Correct 185 ms 19392 KB Ok
3 Correct 3 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 380 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 13 ms 1528 KB Ok
8 Correct 189 ms 19396 KB Ok
9 Correct 97 ms 9916 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 5 ms 680 KB Ok
12 Correct 47 ms 5116 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 399 ms 38956 KB Ok
15 Correct 394 ms 38632 KB Ok
16 Correct 377 ms 38632 KB Ok
17 Correct 196 ms 19564 KB Ok
18 Correct 192 ms 19476 KB Ok
19 Correct 101 ms 9908 KB Ok
20 Correct 92 ms 9864 KB Ok
21 Correct 47 ms 5116 KB Ok
22 Correct 48 ms 5236 KB Ok
23 Correct 25 ms 2808 KB Ok
24 Correct 3 ms 504 KB Ok
25 Correct 3 ms 504 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 379 ms 38552 KB Ok
28 Correct 197 ms 19364 KB Ok
29 Correct 399 ms 38956 KB Ok
30 Correct 24 ms 2808 KB Ok
31 Correct 3 ms 504 KB Ok
32 Correct 13 ms 1528 KB Ok
33 Correct 47 ms 5144 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 380 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 191 ms 19372 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 19384 KB Ok
2 Correct 372 ms 38512 KB Ok
3 Correct 397 ms 38848 KB Ok
4 Correct 25 ms 2808 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 47 ms 5116 KB Ok
7 Correct 404 ms 38632 KB Ok
8 Correct 3 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 4 ms 476 KB Ok
11 Correct 99 ms 9908 KB Ok
12 Correct 194 ms 19472 KB Ok