oj.uz

Submission #396490

# Submission time Handle Problem Language Result Execution time Memory
396490 2021-04-30T04:14:32 Z rama_pang "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 311 ms 6412 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, K, T; string S;
  cin >> N >> K >> T >> S;

  // Adjacent elements in cycle is xored by some value v, where popcount(v) == K.
  // For K = 1, the answer is encoded by "Gray Code". (Or, we could also create
  // the sequence recursively.).
  //
  // Generate all bitmasks with popcount == K. Then, if those bitmasks form a
  // Xor basis with size N, we can generate all 2^N possible bitmasks with those
  // bitmasks in the basis. Note that, since the basis has size N, it is sufficient
  // to solve the case for K = 1 on the basis - this would go through all 2^N
  // possible combinations of basis exactly once, and adjacent only differn in 1
  // ON/OFF basis.
  //
  // Time complexity: O(N 2^N).

  vector<pair<int, int>> basis; // xor basis (reduced value, original value)
  for (int mask = 0; mask < (1 << N); mask++) {
    if (__builtin_popcount(mask) == K) {
      pair<int, int> cur = {mask, mask};
      for (auto i : basis) {
        cur.first = min(cur.first, cur.first ^ i.first);
      }
      if (cur.first == 0) { // not independent
        continue;
      }
      basis.emplace_back(cur);
      for (int i = int(basis.size()) - 2; i >= 0; i--) { // basis is sorted in decreasing order
        if (basis[i].first < basis[i + 1].first) {
          swap(basis[i], basis[i + 1]);
        }
      }
    }
  }

  if (basis.size() != N) { // cannot generate all 2^N masks
    cout << -1 << '\n';
    return 0;
  }

  vector<int> gray(1 << N); // gray code
  for (int mask = 0; mask < (1 << N); mask++) {
    gray[mask] = mask ^ (mask >> 1);
  }

  cout << (1 << N) << '\n';
  for (int mask = 0; mask < (1 << N); mask++) {
    int Xor = 0;
    for (int i = 0; i < N; i++) {
      if ((gray[mask] >> i) & 1) {
        Xor ^= basis[i].second;
      }
    }
    for (int i = 0; i < N; i++) {
      cout << ((S[i] - '0') ^ ((Xor >> i) & 1));
    }
    cout << '\n';
  }
  return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |   if (basis.size() != N) { // cannot generate all 2^N masks
      |       ~~~~~~~~~~~~~^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 6280 KB Ok
2 Correct 129 ms 3144 KB Ok
3 Correct 1 ms 320 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 316 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Ok
2 Correct 9 ms 460 KB Ok
3 Correct 154 ms 3080 KB Ok
4 Correct 63 ms 1604 KB Ok
5 Correct 1 ms 332 KB Ok
6 Correct 3 ms 332 KB Ok
7 Correct 31 ms 956 KB Ok
8 Correct 1 ms 204 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 6320 KB Ok
2 Correct 279 ms 6336 KB Ok
3 Correct 293 ms 6340 KB Ok
4 Correct 132 ms 3168 KB Ok
5 Correct 152 ms 3244 KB Ok
6 Correct 62 ms 1604 KB Ok
7 Correct 62 ms 1640 KB Ok
8 Correct 30 ms 912 KB Ok
9 Correct 30 ms 972 KB Ok
10 Correct 14 ms 592 KB Ok
11 Correct 2 ms 332 KB Ok
12 Correct 1 ms 332 KB Ok
13 Correct 1 ms 204 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 6280 KB Ok
2 Correct 129 ms 3144 KB Ok
3 Correct 1 ms 320 KB Ok
4 Correct 1 ms 204 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 1 ms 204 KB Ok
7 Correct 9 ms 460 KB Ok
8 Correct 154 ms 3080 KB Ok
9 Correct 63 ms 1604 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 3 ms 332 KB Ok
12 Correct 31 ms 956 KB Ok
13 Correct 1 ms 204 KB Ok
14 Correct 276 ms 6320 KB Ok
15 Correct 279 ms 6336 KB Ok
16 Correct 293 ms 6340 KB Ok
17 Correct 132 ms 3168 KB Ok
18 Correct 152 ms 3244 KB Ok
19 Correct 62 ms 1604 KB Ok
20 Correct 62 ms 1640 KB Ok
21 Correct 30 ms 912 KB Ok
22 Correct 30 ms 972 KB Ok
23 Correct 14 ms 592 KB Ok
24 Correct 2 ms 332 KB Ok
25 Correct 1 ms 332 KB Ok
26 Correct 1 ms 204 KB Ok
27 Correct 290 ms 6236 KB Ok
28 Correct 130 ms 3140 KB Ok
29 Correct 279 ms 6284 KB Ok
30 Correct 14 ms 516 KB Ok
31 Correct 1 ms 332 KB Ok
32 Correct 7 ms 460 KB Ok
33 Correct 30 ms 872 KB Ok
34 Correct 1 ms 204 KB Ok
35 Correct 1 ms 204 KB Ok
36 Correct 1 ms 332 KB Ok
37 Correct 1 ms 312 KB Ok
38 Correct 132 ms 3264 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 3136 KB Ok
2 Correct 311 ms 6412 KB Ok
3 Correct 284 ms 6360 KB Ok
4 Correct 15 ms 588 KB Ok
5 Correct 1 ms 204 KB Ok
6 Correct 30 ms 936 KB Ok
7 Correct 273 ms 6332 KB Ok
8 Correct 1 ms 332 KB Ok
9 Correct 1 ms 204 KB Ok
10 Correct 1 ms 332 KB Ok
11 Correct 62 ms 1648 KB Ok
12 Correct 133 ms 3188 KB Ok