oj.uz

Submission #151294

# Submission time Handle Problem Language Result Execution time Memory
151294 2019-09-02T12:00:20 Z andrew "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 996 ms 39008 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);

    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 995 ms 964 KB Ok
2 Correct 996 ms 18232 KB Ok
3 Correct 996 ms 9576 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 394 ms 38660 KB Ok
2 Correct 185 ms 19440 KB Ok
3 Correct 3 ms 500 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 2 ms 376 KB Ok
2 Correct 14 ms 1592 KB Ok
3 Correct 194 ms 19464 KB Ok
4 Correct 96 ms 9856 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 5 ms 632 KB Ok
7 Correct 47 ms 5116 KB Ok
8 Correct 2 ms 380 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 39008 KB Ok
2 Correct 397 ms 38768 KB Ok
3 Correct 386 ms 38624 KB Ok
4 Correct 196 ms 19592 KB Ok
5 Correct 194 ms 19448 KB Ok
6 Correct 99 ms 10036 KB Ok
7 Correct 93 ms 9972 KB Ok
8 Correct 47 ms 5116 KB Ok
9 Correct 49 ms 5208 KB Ok
10 Correct 25 ms 2748 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 394 ms 38660 KB Ok
2 Correct 185 ms 19440 KB Ok
3 Correct 3 ms 500 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 14 ms 1592 KB Ok
8 Correct 194 ms 19464 KB Ok
9 Correct 96 ms 9856 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 5 ms 632 KB Ok
12 Correct 47 ms 5116 KB Ok
13 Correct 2 ms 380 KB Ok
14 Correct 408 ms 39008 KB Ok
15 Correct 397 ms 38768 KB Ok
16 Correct 386 ms 38624 KB Ok
17 Correct 196 ms 19592 KB Ok
18 Correct 194 ms 19448 KB Ok
19 Correct 99 ms 10036 KB Ok
20 Correct 93 ms 9972 KB Ok
21 Correct 47 ms 5116 KB Ok
22 Correct 49 ms 5208 KB Ok
23 Correct 25 ms 2748 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 373 ms 38640 KB Ok
28 Correct 196 ms 19504 KB Ok
29 Correct 401 ms 38880 KB Ok
30 Correct 25 ms 2808 KB Ok
31 Correct 4 ms 504 KB Ok
32 Correct 13 ms 1528 KB Ok
33 Correct 47 ms 5104 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 191 ms 19432 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 19484 KB Ok
2 Correct 378 ms 38632 KB Ok
3 Correct 396 ms 38828 KB Ok
4 Correct 25 ms 2808 KB Ok
5 Correct 3 ms 376 KB Ok
6 Correct 49 ms 5116 KB Ok
7 Correct 389 ms 38764 KB Ok
8 Correct 4 ms 504 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 4 ms 504 KB Ok
11 Correct 100 ms 9860 KB Ok
12 Correct 200 ms 19384 KB Ok