oj.uz

Submission #151288

# Submission time Handle Problem Language Result Execution time Memory
151288 2019-09-02T11:55:55 Z andrew "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 1000 ms 38916 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){
    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:70: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 Execution timed out 1076 ms 888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 38508 KB Ok
2 Correct 61 ms 19440 KB Ok
3 Correct 2 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Ok
2 Correct 5 ms 1528 KB Ok
3 Correct 66 ms 19448 KB Ok
4 Correct 34 ms 9820 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 632 KB Ok
7 Correct 17 ms 5120 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 38824 KB Ok
2 Correct 140 ms 38600 KB Ok
3 Correct 130 ms 38600 KB Ok
4 Correct 71 ms 19564 KB Ok
5 Correct 67 ms 19428 KB Ok
6 Correct 40 ms 9840 KB Ok
7 Correct 31 ms 9868 KB Ok
8 Correct 15 ms 5116 KB Ok
9 Correct 17 ms 5208 KB Ok
10 Correct 9 ms 2808 KB Ok
11 Correct 2 ms 504 KB Ok
12 Correct 2 ms 476 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 38508 KB Ok
2 Correct 61 ms 19440 KB Ok
3 Correct 2 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 396 KB Ok
7 Correct 5 ms 1528 KB Ok
8 Correct 66 ms 19448 KB Ok
9 Correct 34 ms 9820 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 632 KB Ok
12 Correct 17 ms 5120 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 145 ms 38824 KB Ok
15 Correct 140 ms 38600 KB Ok
16 Correct 130 ms 38600 KB Ok
17 Correct 71 ms 19564 KB Ok
18 Correct 67 ms 19428 KB Ok
19 Correct 40 ms 9840 KB Ok
20 Correct 31 ms 9868 KB Ok
21 Correct 15 ms 5116 KB Ok
22 Correct 17 ms 5208 KB Ok
23 Correct 9 ms 2808 KB Ok
24 Correct 2 ms 504 KB Ok
25 Correct 2 ms 476 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 126 ms 38576 KB Ok
28 Correct 73 ms 19480 KB Ok
29 Correct 145 ms 38916 KB Ok
30 Correct 10 ms 2808 KB Ok
31 Correct 2 ms 504 KB Ok
32 Correct 5 ms 1528 KB Ok
33 Correct 16 ms 5372 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 348 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 3 ms 376 KB Ok
38 Correct 66 ms 19444 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19412 KB Ok
2 Correct 124 ms 38588 KB Ok
3 Correct 155 ms 38888 KB Ok
4 Correct 9 ms 2808 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 17 ms 5116 KB Ok
7 Correct 138 ms 38632 KB Ok
8 Correct 2 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 2 ms 504 KB Ok
11 Correct 33 ms 9816 KB Ok
12 Correct 70 ms 19472 KB Ok