oj.uz

Submission #343235

# Submission time Handle Problem Language Result Execution time Memory
343235 2021-01-03T14:50:49 Z IZhO_2021_I_want_Silver "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 372 ms 35408 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <stack>
#include <queue>
#include <bitset>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>-

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

// template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  order_of_key (k) : Number of items strictly smaller than k .
//  find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define show(a) cerr << #a <<" -> "<< a <<" "
#define nl cerr <<"\n"
//#define int ll

const int N = 3e5 + 5;
const int oo = 1e9 + 5;

int n, k, t;
bitset <N> was;
vector <int> vec, good;
string s;

void show_bits(int x) {
    for (int i = 0; i < n; ++i) {
        if (x & (1 << i)) { cout << 1; }
        else { cout << 0; }
    }
    cout << "\n";
}

void go(int pos) {
    if (pos == (1 << n) + 1) {
        if (t == 1) {
            if (__builtin_popcount(vec[0] ^ vec.back()) == k) {
                cout << sz(vec) <<"\n";
                for (int i = 0; i < sz(vec); ++i) {
                    show_bits(vec[i]);
                }
                exit(0);
            }
        }
        else {
            cout << sz(vec) <<"\n";
            for (int i = 0; i < sz(vec); ++i) {
                show_bits(vec[i]);
            }
            exit(0);
        }
        return;
    }
    for (int i = 0; i < sz(good); ++i) {
        int x = (vec.back() ^ good[i]);
        if (was[x]) { continue; }
        if (__builtin_popcount((vec.back() ^ x)) != k) { continue; }

        was[x] = 1;
        vec.pb(x);
        go(pos + 1);
        was[x] = 0;
        vec.ppb();
    }
}

void solve() {
    cin >> n >> k >> t;
    cin >> s;

    if (k % 2 == 0) { cout << -1; return; }

    for (int i = 0; i < (1 << n); ++i) {
        if (__builtin_popcount(i) == k) { good.pb(i); }
    }

    int x = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') { x += (1 << i); }
    }
    was[x] = 1;
    vec.pb(x);
    go(2);
}

 main () {
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	int tests = 1;
	//cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Just Chalish!
*/

Compilation message

lyuboyn.cpp:106:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 |  main () {
      |        ^

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 1 ms 364 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 0 ms 364 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 35312 KB Ok
2 Correct 158 ms 17772 KB Ok
3 Correct 1 ms 492 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 8 ms 1388 KB Ok
3 Correct 189 ms 17664 KB Ok
4 Correct 77 ms 9064 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 620 KB Ok
7 Correct 36 ms 4716 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 35328 KB Ok
2 Correct 343 ms 35380 KB Ok
3 Correct 337 ms 35296 KB Ok
4 Correct 164 ms 17764 KB Ok
5 Correct 159 ms 17764 KB Ok
6 Correct 78 ms 9064 KB Ok
7 Correct 74 ms 9064 KB Ok
8 Correct 36 ms 4716 KB Ok
9 Correct 38 ms 4716 KB Ok
10 Correct 17 ms 2540 KB Ok
11 Correct 2 ms 492 KB Ok
12 Correct 1 ms 492 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 35312 KB Ok
2 Correct 158 ms 17772 KB Ok
3 Correct 1 ms 492 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 8 ms 1388 KB Ok
8 Correct 189 ms 17664 KB Ok
9 Correct 77 ms 9064 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 2 ms 620 KB Ok
12 Correct 36 ms 4716 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 340 ms 35328 KB Ok
15 Correct 343 ms 35380 KB Ok
16 Correct 337 ms 35296 KB Ok
17 Correct 164 ms 17764 KB Ok
18 Correct 159 ms 17764 KB Ok
19 Correct 78 ms 9064 KB Ok
20 Correct 74 ms 9064 KB Ok
21 Correct 36 ms 4716 KB Ok
22 Correct 38 ms 4716 KB Ok
23 Correct 17 ms 2540 KB Ok
24 Correct 2 ms 492 KB Ok
25 Correct 1 ms 492 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 365 ms 35296 KB Ok
28 Correct 157 ms 17692 KB Ok
29 Correct 338 ms 35388 KB Ok
30 Correct 18 ms 2540 KB Ok
31 Correct 1 ms 492 KB Ok
32 Correct 9 ms 1388 KB Ok
33 Correct 38 ms 4716 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 168 ms 17664 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 17672 KB Ok
2 Correct 345 ms 35296 KB Ok
3 Correct 345 ms 35408 KB Ok
4 Correct 18 ms 2540 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 35 ms 4716 KB Ok
7 Correct 372 ms 35296 KB Ok
8 Correct 1 ms 492 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 3 ms 492 KB Ok
11 Correct 74 ms 8964 KB Ok
12 Correct 157 ms 17764 KB Ok