oj.uz

Submission #151291

# Submission time Handle Problem Language Result Execution time Memory
151291 2019-09-02T11:58:23 Z andrew "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 1000 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){
    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 3 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 1069 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 120 ms 38544 KB Ok
2 Correct 59 ms 19332 KB Ok
3 Correct 3 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 376 KB Ok
2 Correct 5 ms 1488 KB Ok
3 Correct 67 ms 19448 KB Ok
4 Correct 34 ms 9724 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 632 KB Ok
7 Correct 16 ms 5116 KB Ok
8 Correct 2 ms 348 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 38768 KB Ok
2 Correct 155 ms 38728 KB Ok
3 Correct 135 ms 38552 KB Ok
4 Correct 72 ms 19564 KB Ok
5 Correct 65 ms 19448 KB Ok
6 Correct 36 ms 9840 KB Ok
7 Correct 31 ms 9844 KB Ok
8 Correct 16 ms 5240 KB Ok
9 Correct 17 ms 5236 KB Ok
10 Correct 9 ms 2808 KB Ok
11 Correct 2 ms 504 KB Ok
12 Correct 2 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 120 ms 38544 KB Ok
2 Correct 59 ms 19332 KB Ok
3 Correct 3 ms 504 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 5 ms 1488 KB Ok
8 Correct 67 ms 19448 KB Ok
9 Correct 34 ms 9724 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 632 KB Ok
12 Correct 16 ms 5116 KB Ok
13 Correct 2 ms 348 KB Ok
14 Correct 146 ms 38768 KB Ok
15 Correct 155 ms 38728 KB Ok
16 Correct 135 ms 38552 KB Ok
17 Correct 72 ms 19564 KB Ok
18 Correct 65 ms 19448 KB Ok
19 Correct 36 ms 9840 KB Ok
20 Correct 31 ms 9844 KB Ok
21 Correct 16 ms 5240 KB Ok
22 Correct 17 ms 5236 KB Ok
23 Correct 9 ms 2808 KB Ok
24 Correct 2 ms 504 KB Ok
25 Correct 2 ms 504 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 123 ms 38600 KB Ok
28 Correct 70 ms 19444 KB Ok
29 Correct 147 ms 38836 KB Ok
30 Correct 9 ms 2808 KB Ok
31 Correct 2 ms 504 KB Ok
32 Correct 6 ms 1528 KB Ok
33 Correct 16 ms 5116 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 2 ms 504 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 66 ms 19440 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19412 KB Ok
2 Correct 127 ms 38508 KB Ok
3 Correct 146 ms 38888 KB Ok
4 Correct 9 ms 2808 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 16 ms 5116 KB Ok
7 Correct 152 ms 38604 KB Ok
8 Correct 2 ms 504 KB Ok
9 Correct 2 ms 380 KB Ok
10 Correct 3 ms 504 KB Ok
11 Correct 32 ms 9892 KB Ok
12 Correct 76 ms 19504 KB Ok