oj.uz

Submission #346689

# Submission time Handle Problem Language Result Execution time Memory
346689 2021-01-10T17:25:53 Z milleniumEeee "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 658 ms 49120 KB 
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

vector <int> good;

bool used[(1 << 18)];
int cnt = 0;
int start = 0;
int n, k, t;

int par[(1 << 18)];

string binary(int x) {
  string s = "";
  for (int i = 0; i < n; i++) {
    if (x & (1 << i)) {
      s += '1';
    } else {
      s += '0';
    }
  }
  return s;
}

void dfs(int v, int sz = 1) {
  if (sz == cnt) {
    if ((t == 0) || (t == 1 && __builtin_popcount((v ^ start)) == k)) {
      vector <int> path;
      int fn = v;
      while (fn != start) {
        path.push_back(fn);
        fn = par[fn];
      }
      path.push_back(start);
      reverse(all(path));
      cout << cnt << endl;
      for (int el : path) {
        cout << binary(el) << endl;
      }
      exit(0);
    }
  } else {
    for (int mask : good) {
      int nxt = (v ^ mask);
      if (!used[nxt]) {
        par[nxt] = v;
        used[nxt] = 1;
        dfs(nxt, sz + 1);
        par[nxt] = -1;
        used[nxt] = 0;
      }
    }
  }
}

signed main() {
  cin >> n >> k >> t;
  if (k % 2 == 0) {
    return cout << -1, 0;
  }
  string s;
  cin >> s;
  for (int i = 0; i < n; i++) {
    if (s[i] == '1') {
      start += (1 << i);
    }
  }
  for (int mask = 0; mask < (1 << n); mask++) {
    if (__builtin_popcount(mask) == k) {
      good.push_back(mask);
    }
  }
  cnt = (1 << n);
  memset(par, -1, sizeof (par));
  used[start] = 1;
  dfs(start);
  // в любом случае найдёт
}

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 364 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 48936 KB Ok
2 Correct 322 ms 25060 KB Ok
3 Correct 4 ms 1516 KB Ok
4 Correct 1 ms 1388 KB Ok
5 Correct 1 ms 1388 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1388 KB Ok
2 Correct 20 ms 2796 KB Ok
3 Correct 325 ms 25104 KB Ok
4 Correct 161 ms 13264 KB Ok
5 Correct 2 ms 1388 KB Ok
6 Correct 6 ms 1644 KB Ok
7 Correct 80 ms 7276 KB Ok
8 Correct 2 ms 1388 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 48864 KB Ok
2 Correct 652 ms 49120 KB Ok
3 Correct 644 ms 48864 KB Ok
4 Correct 320 ms 25060 KB Ok
5 Correct 325 ms 25060 KB Ok
6 Correct 165 ms 13160 KB Ok
7 Correct 161 ms 13160 KB Ok
8 Correct 78 ms 7404 KB Ok
9 Correct 80 ms 7404 KB Ok
10 Correct 41 ms 4332 KB Ok
11 Correct 3 ms 1516 KB Ok
12 Correct 3 ms 1516 KB Ok
13 Correct 2 ms 1388 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 48936 KB Ok
2 Correct 322 ms 25060 KB Ok
3 Correct 4 ms 1516 KB Ok
4 Correct 1 ms 1388 KB Ok
5 Correct 1 ms 1388 KB Ok
6 Correct 1 ms 1388 KB Ok
7 Correct 20 ms 2796 KB Ok
8 Correct 325 ms 25104 KB Ok
9 Correct 161 ms 13264 KB Ok
10 Correct 2 ms 1388 KB Ok
11 Correct 6 ms 1644 KB Ok
12 Correct 80 ms 7276 KB Ok
13 Correct 2 ms 1388 KB Ok
14 Correct 643 ms 48864 KB Ok
15 Correct 652 ms 49120 KB Ok
16 Correct 644 ms 48864 KB Ok
17 Correct 320 ms 25060 KB Ok
18 Correct 325 ms 25060 KB Ok
19 Correct 165 ms 13160 KB Ok
20 Correct 161 ms 13160 KB Ok
21 Correct 78 ms 7404 KB Ok
22 Correct 80 ms 7404 KB Ok
23 Correct 41 ms 4332 KB Ok
24 Correct 3 ms 1516 KB Ok
25 Correct 3 ms 1516 KB Ok
26 Correct 2 ms 1388 KB Ok
27 Correct 658 ms 48908 KB Ok
28 Correct 329 ms 25096 KB Ok
29 Correct 648 ms 48864 KB Ok
30 Correct 40 ms 4332 KB Ok
31 Correct 4 ms 1516 KB Ok
32 Correct 21 ms 2796 KB Ok
33 Correct 81 ms 7276 KB Ok
34 Correct 2 ms 1388 KB Ok
35 Correct 1 ms 1388 KB Ok
36 Correct 2 ms 1388 KB Ok
37 Correct 1 ms 1388 KB Ok
38 Correct 327 ms 25060 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 25036 KB Ok
2 Correct 655 ms 48856 KB Ok
3 Correct 640 ms 48992 KB Ok
4 Correct 40 ms 4332 KB Ok
5 Correct 2 ms 1388 KB Ok
6 Correct 79 ms 7276 KB Ok
7 Correct 645 ms 49120 KB Ok
8 Correct 4 ms 1792 KB Ok
9 Correct 1 ms 1388 KB Ok
10 Correct 3 ms 1516 KB Ok
11 Correct 164 ms 13236 KB Ok
12 Correct 326 ms 25060 KB Ok