oj.uz

Submission #151293

# Submission time Handle Problem Language Result Execution time Memory
151293 2019-09-02T11:59:18 Z andrew "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 951 ms 38888 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.95)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);

    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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 972 KB Ok
2 Correct 951 ms 18232 KB Ok
3 Correct 950 ms 9684 KB Ok
4 Incorrect 2 ms 376 KB Unexpected end of file - int32 expected
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 38556 KB Ok
2 Correct 184 ms 19444 KB Ok
3 Correct 3 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 3 ms 376 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Ok
2 Correct 13 ms 1528 KB Ok
3 Correct 193 ms 19428 KB Ok
4 Correct 95 ms 9852 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 5 ms 632 KB Ok
7 Correct 46 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 38780 KB Ok
2 Correct 383 ms 38760 KB Ok
3 Correct 379 ms 38676 KB Ok
4 Correct 201 ms 19600 KB Ok
5 Correct 192 ms 19492 KB Ok
6 Correct 97 ms 9840 KB Ok
7 Correct 92 ms 9972 KB Ok
8 Correct 46 ms 5116 KB Ok
9 Correct 48 ms 5168 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 371 ms 38556 KB Ok
2 Correct 184 ms 19444 KB Ok
3 Correct 3 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 13 ms 1528 KB Ok
8 Correct 193 ms 19428 KB Ok
9 Correct 95 ms 9852 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 5 ms 632 KB Ok
12 Correct 46 ms 5116 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 399 ms 38780 KB Ok
15 Correct 383 ms 38760 KB Ok
16 Correct 379 ms 38676 KB Ok
17 Correct 201 ms 19600 KB Ok
18 Correct 192 ms 19492 KB Ok
19 Correct 97 ms 9840 KB Ok
20 Correct 92 ms 9972 KB Ok
21 Correct 46 ms 5116 KB Ok
22 Correct 48 ms 5168 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 378 ms 38660 KB Ok
28 Correct 196 ms 19472 KB Ok
29 Correct 397 ms 38888 KB Ok
30 Correct 25 ms 2808 KB Ok
31 Correct 3 ms 504 KB Ok
32 Correct 13 ms 1528 KB Ok
33 Correct 47 ms 5200 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 189 ms 19444 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 19364 KB Ok
2 Correct 380 ms 38528 KB Ok
3 Correct 399 ms 38784 KB Ok
4 Correct 25 ms 2808 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 51 ms 5244 KB Ok
7 Correct 413 ms 38724 KB Ok
8 Correct 3 ms 508 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 4 ms 504 KB Ok
11 Correct 94 ms 9840 KB Ok
12 Correct 201 ms 19556 KB Ok