oj.uz

Submission #569224

# Submission time Handle Problem Language Result Execution time Memory
569224 2022-05-27T05:28:13 Z SSRS "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 593 ms 6632 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> solve(int N, int K, int t){
  if (K == N - 1){
    vector<int> ans(1 << N);
    ans[0] = t;
    for (int i = 1; i < (1 << N); i++){
      ans[i] = ans[i - 1] ^ ((1 << N) - 1);
      int p = __builtin_ctz(i);
      ans[i] ^= 1 << p;
    }
    return ans;
  } else {
    vector<int> P1 = solve(N - 1, K, t);
    int r = P1.back();
    int r2 = r ^ ((1 << (K - 1)) - 1);
    vector<int> P2 = solve(N - 1, K, r2);
    vector<int> P;
    for (int i = 0; i < (1 << (N - 1)); i++){
      P.push_back(P1[i]);
    }
    for (int i = 0; i < (1 << (N - 1)); i++){
      P.push_back(P2[i] ^ (1 << (N - 1)));
    }
    return P;
  }
}
int main(){
  int N, K, T;
  cin >> N >> K >> T;
  string S;
  cin >> S;
  int s = 0;
  for (int i = 0; i < N; i++){
    if (S[i] == '1'){
      s += 1 << (N - 1 - i);
    }
  }
  if (N == 1){
    cout << 2 << endl;
    cout << s << endl;
    cout << (s ^ 1) << endl;
  } else if (K % 2 == 0 || N == K){
    cout << -1 << endl;
  } else {
    vector<int> P = solve(N, K, 0);
    for (int i = 0; i < (1 << N); i++){
      if (P[i] == s){
        rotate(P.begin(), P.begin() + i, P.end());
      }
    }
    cout << (1 << N) << endl;
    for (int i = 0; i < (1 << N); i++){
      for (int j = N - 1; j >= 0; j--){
        cout << (P[i] >> j & 1);
      }
      cout << endl;
    }
  }
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 6496 KB Ok
2 Correct 270 ms 3268 KB Ok
3 Correct 2 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 19 ms 468 KB Ok
3 Correct 277 ms 3376 KB Ok
4 Correct 135 ms 1820 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 4 ms 340 KB Ok
7 Correct 62 ms 1148 KB Ok
8 Correct 1 ms 212 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 6336 KB Ok
2 Correct 534 ms 6456 KB Ok
3 Correct 532 ms 6400 KB Ok
4 Correct 263 ms 3252 KB Ok
5 Correct 267 ms 3348 KB Ok
6 Correct 132 ms 1772 KB Ok
7 Correct 127 ms 1788 KB Ok
8 Correct 65 ms 1176 KB Ok
9 Correct 63 ms 1184 KB Ok
10 Correct 29 ms 652 KB Ok
11 Correct 2 ms 212 KB Ok
12 Correct 3 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 6496 KB Ok
2 Correct 270 ms 3268 KB Ok
3 Correct 2 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 19 ms 468 KB Ok
8 Correct 277 ms 3376 KB Ok
9 Correct 135 ms 1820 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 4 ms 340 KB Ok
12 Correct 62 ms 1148 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 550 ms 6336 KB Ok
15 Correct 534 ms 6456 KB Ok
16 Correct 532 ms 6400 KB Ok
17 Correct 263 ms 3252 KB Ok
18 Correct 267 ms 3348 KB Ok
19 Correct 132 ms 1772 KB Ok
20 Correct 127 ms 1788 KB Ok
21 Correct 65 ms 1176 KB Ok
22 Correct 63 ms 1184 KB Ok
23 Correct 29 ms 652 KB Ok
24 Correct 2 ms 212 KB Ok
25 Correct 3 ms 212 KB Ok
26 Correct 1 ms 212 KB Ok
27 Correct 526 ms 6268 KB Ok
28 Correct 259 ms 3404 KB Ok
29 Correct 544 ms 6496 KB Ok
30 Correct 33 ms 700 KB Ok
31 Correct 2 ms 212 KB Ok
32 Correct 16 ms 432 KB Ok
33 Correct 61 ms 1112 KB Ok
34 Correct 1 ms 212 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 1 ms 300 KB Ok
37 Correct 1 ms 212 KB Ok
38 Correct 271 ms 3192 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 3288 KB Ok
2 Correct 545 ms 6296 KB Ok
3 Correct 593 ms 6504 KB Ok
4 Correct 40 ms 628 KB Ok
5 Correct 2 ms 300 KB Ok
6 Correct 65 ms 1148 KB Ok
7 Correct 516 ms 6632 KB Ok
8 Correct 2 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 2 ms 300 KB Ok
11 Correct 118 ms 1616 KB Ok
12 Correct 252 ms 3388 KB Ok