oj.uz

Submission #378380

# Submission time Handle Problem Language Result Execution time Memory
378380 2021-03-16T15:31:46 Z abc864197532 "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 841 ms 6616 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 200000, logN = 18, K = 333;

vector <int> gray_code(int n) {
    if (n == 1) return {0, 1};
    vector <int> under = gray_code(n - 1);
    vector <int> ans;
    for (int i : under) ans.pb(i);
    reverse(all(under));
    for (int i : under) ans.pb(i | (1 << n - 1));
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, t;
    string str;
    cin >> n >> k >> t >> str;
    int from = 0;
    for (int i = 0; i < n; ++i) from = (from << 1) | (str[i] == '1');
    if (k & 1 ^ 1) {
        cout << -1 << endl;
        return 0;
    }
    auto output = [&](int v) {
        v ^= from;
        for (int i = n - 1; ~i; --i) cout << (v >> i & 1);
        cout << endl;
    };
    cout << (1 << n) << endl;
    if (k == 1) {
        vector <int> ans = gray_code(n);
        for (int i : ans) output(i);
        return 0;
    }
    k >>= 1;
    vector <int> right = gray_code(k * 2);
    vector <int> lefta = gray_code(n - k * 2), leftb = lefta;
    for (int i = 0; i < leftb.size(); ++i) {
        leftb[i] ^= (1 << n - k * 2 - 2);
    }
    for (int i = 0; i < right.size(); ++i) {
        if (i & 1 ^ 1) {
            for (int j = 0; j < lefta.size(); ++j) {
                output(lefta[j] << (k * 2) | right[i]);
                right[i] ^= ((1 << k * 2) - 1);
            }
        } else {
            for (int j = 0; j < leftb.size(); ++j) {
                output(leftb[j] << (k * 2) | right[i]);
                right[i] ^= ((1 << k * 2) - 1);
            }
        }
    }
}

Compilation message

lyuboyn.cpp: In function 'std::vector<int> gray_code(int)':
lyuboyn.cpp:34:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |     for (int i : under) ans.pb(i | (1 << n - 1));
      |                                          ~~^~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:46:11: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   46 |     if (k & 1 ^ 1) {
      |         ~~^~~
lyuboyn.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < leftb.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
lyuboyn.cpp:65:37: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   65 |         leftb[i] ^= (1 << n - k * 2 - 2);
      |                           ~~~~~~~~~~^~~
lyuboyn.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < right.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
lyuboyn.cpp:68:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   68 |         if (i & 1 ^ 1) {
      |             ~~^~~
lyuboyn.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j = 0; j < lefta.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~
lyuboyn.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int j = 0; j < leftb.size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~

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 0 ms 364 KB Ok
3 Correct 0 ms 364 KB Ok
4 Correct 0 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 0 ms 364 KB Ok
7 Correct 0 ms 364 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 6616 KB Ok
2 Correct 424 ms 3296 KB Ok
3 Correct 3 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 27 ms 492 KB Ok
3 Correct 403 ms 3080 KB Ok
4 Correct 198 ms 1900 KB Ok
5 Correct 2 ms 364 KB Ok
6 Correct 8 ms 364 KB Ok
7 Correct 96 ms 1004 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 5484 KB Ok
2 Correct 803 ms 5700 KB Ok
3 Correct 811 ms 6120 KB Ok
4 Correct 404 ms 2796 KB Ok
5 Correct 401 ms 3056 KB Ok
6 Correct 198 ms 1516 KB Ok
7 Correct 196 ms 1896 KB Ok
8 Correct 97 ms 1004 KB Ok
9 Correct 100 ms 876 KB Ok
10 Correct 53 ms 620 KB Ok
11 Correct 4 ms 364 KB Ok
12 Correct 3 ms 364 KB Ok
13 Correct 2 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 6616 KB Ok
2 Correct 424 ms 3296 KB Ok
3 Correct 3 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 27 ms 492 KB Ok
8 Correct 403 ms 3080 KB Ok
9 Correct 198 ms 1900 KB Ok
10 Correct 2 ms 364 KB Ok
11 Correct 8 ms 364 KB Ok
12 Correct 96 ms 1004 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 801 ms 5484 KB Ok
15 Correct 803 ms 5700 KB Ok
16 Correct 811 ms 6120 KB Ok
17 Correct 404 ms 2796 KB Ok
18 Correct 401 ms 3056 KB Ok
19 Correct 198 ms 1516 KB Ok
20 Correct 196 ms 1896 KB Ok
21 Correct 97 ms 1004 KB Ok
22 Correct 100 ms 876 KB Ok
23 Correct 53 ms 620 KB Ok
24 Correct 4 ms 364 KB Ok
25 Correct 3 ms 364 KB Ok
26 Correct 2 ms 364 KB Ok
27 Correct 841 ms 5980 KB Ok
28 Correct 400 ms 2924 KB Ok
29 Correct 811 ms 5548 KB Ok
30 Correct 48 ms 620 KB Ok
31 Correct 4 ms 364 KB Ok
32 Correct 23 ms 492 KB Ok
33 Correct 96 ms 876 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 2 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 397 ms 3052 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 3180 KB Ok
2 Correct 823 ms 5864 KB Ok
3 Correct 820 ms 5464 KB Ok
4 Correct 47 ms 620 KB Ok
5 Correct 3 ms 364 KB Ok
6 Correct 96 ms 876 KB Ok
7 Correct 806 ms 5644 KB Ok
8 Correct 4 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 4 ms 364 KB Ok
11 Correct 194 ms 1816 KB Ok
12 Correct 397 ms 3056 KB Ok