oj.uz

Submission #343243

# Submission time Handle Problem Language Result Execution time Memory
343243 2021-01-03T15:01:01 Z IZhO_2021_I_want_Silver "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 291 ms 23144 KB 
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

#define sz(a) (int)a.size()
#define pb push_back
#define ppb pop_back

const int N = 3e5 + 5;

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

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);
    was[x] = 0;
    vec.ppb();

    return;
}

 main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tests = 1;
	//cin >> tests;
	while (tests --) {
		solve();
	}
	return 0;
}
/*
    Ускоренный перебор правильного порядка
    * может быстро и легко находится подходящий?
    * max размер vector good -> 48000
    * по сути это ускоренный слоу
        * вместо того чтобы перебирать (1 << n) = 2 * 10^5 элементов и проверять биты,
        * мы делаем массив good где все гаходим легко подходящий по битам
          и проверяем не более 48000 элементов
*/

Compilation message

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

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 364 KB Ok
3 Correct 0 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 0 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 0 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 277 ms 23016 KB Ok
2 Correct 132 ms 11628 KB Ok
3 Correct 1 ms 364 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 7 ms 1004 KB Ok
3 Correct 133 ms 11656 KB Ok
4 Correct 63 ms 6128 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 492 KB Ok
7 Correct 30 ms 3180 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 23136 KB Ok
2 Correct 280 ms 23008 KB Ok
3 Correct 280 ms 23016 KB Ok
4 Correct 133 ms 11620 KB Ok
5 Correct 132 ms 11628 KB Ok
6 Correct 66 ms 6028 KB Ok
7 Correct 62 ms 6000 KB Ok
8 Correct 30 ms 3180 KB Ok
9 Correct 30 ms 3308 KB Ok
10 Correct 18 ms 1772 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 23016 KB Ok
2 Correct 132 ms 11628 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 7 ms 1004 KB Ok
8 Correct 133 ms 11656 KB Ok
9 Correct 63 ms 6128 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 2 ms 492 KB Ok
12 Correct 30 ms 3180 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 291 ms 23136 KB Ok
15 Correct 280 ms 23008 KB Ok
16 Correct 280 ms 23016 KB Ok
17 Correct 133 ms 11620 KB Ok
18 Correct 132 ms 11628 KB Ok
19 Correct 66 ms 6028 KB Ok
20 Correct 62 ms 6000 KB Ok
21 Correct 30 ms 3180 KB Ok
22 Correct 30 ms 3308 KB Ok
23 Correct 18 ms 1772 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 286 ms 23016 KB Ok
28 Correct 136 ms 11768 KB Ok
29 Correct 278 ms 23136 KB Ok
30 Correct 14 ms 1772 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 7 ms 1144 KB Ok
33 Correct 30 ms 3180 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 136 ms 11756 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 11628 KB Ok
2 Correct 286 ms 23144 KB Ok
3 Correct 283 ms 23136 KB Ok
4 Correct 14 ms 1772 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 33 ms 3180 KB Ok
7 Correct 276 ms 22976 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 64 ms 6000 KB Ok
12 Correct 136 ms 11896 KB Ok