oj.uz

Submission #346688

# Submission time Handle Problem Language Result Execution time Memory
346688 2021-01-10T17:24:30 Z milleniumEeee "The Lyuboyn" code (IZhO19_lyuboyn) C++17
97 / 100
 1000 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;
  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);
  cout << -1 << endl;
}

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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 48864 KB Ok
2 Correct 331 ms 25008 KB Ok
3 Correct 3 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 2 ms 1388 KB Ok
2 Correct 23 ms 2796 KB Ok
3 Correct 326 ms 25060 KB Ok
4 Correct 161 ms 13160 KB Ok
5 Correct 2 ms 1388 KB Ok
6 Correct 6 ms 1644 KB Ok
7 Correct 78 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 667 ms 49064 KB Ok
2 Correct 651 ms 48992 KB Ok
3 Correct 654 ms 49120 KB Ok
4 Correct 326 ms 25060 KB Ok
5 Correct 326 ms 25060 KB Ok
6 Correct 169 ms 13160 KB Ok
7 Correct 159 ms 13160 KB Ok
8 Correct 78 ms 7276 KB Ok
9 Correct 79 ms 7276 KB Ok
10 Correct 40 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 650 ms 48864 KB Ok
2 Correct 331 ms 25008 KB Ok
3 Correct 3 ms 1516 KB Ok
4 Correct 1 ms 1388 KB Ok
5 Correct 1 ms 1388 KB Ok
6 Correct 2 ms 1388 KB Ok
7 Correct 23 ms 2796 KB Ok
8 Correct 326 ms 25060 KB Ok
9 Correct 161 ms 13160 KB Ok
10 Correct 2 ms 1388 KB Ok
11 Correct 6 ms 1644 KB Ok
12 Correct 78 ms 7276 KB Ok
13 Correct 2 ms 1388 KB Ok
14 Correct 667 ms 49064 KB Ok
15 Correct 651 ms 48992 KB Ok
16 Correct 654 ms 49120 KB Ok
17 Correct 326 ms 25060 KB Ok
18 Correct 326 ms 25060 KB Ok
19 Correct 169 ms 13160 KB Ok
20 Correct 159 ms 13160 KB Ok
21 Correct 78 ms 7276 KB Ok
22 Correct 79 ms 7276 KB Ok
23 Correct 40 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 665 ms 48864 KB Ok
28 Correct 326 ms 25060 KB Ok
29 Correct 646 ms 49000 KB Ok
30 Correct 40 ms 4332 KB Ok
31 Correct 3 ms 1516 KB Ok
32 Correct 21 ms 2924 KB Ok
33 Correct 79 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 1404 KB Ok
38 Correct 324 ms 25060 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 25060 KB Ok
2 Correct 656 ms 48936 KB Ok
3 Correct 644 ms 49012 KB Ok
4 Correct 39 ms 4332 KB Ok
5 Correct 2 ms 1388 KB Ok
6 Correct 82 ms 7276 KB Ok
7 Correct 651 ms 48992 KB Ok
8 Correct 3 ms 1516 KB Ok
9 Correct 1 ms 1388 KB Ok
10 Correct 3 ms 1516 KB Ok
11 Correct 163 ms 13288 KB Ok
12 Correct 324 ms 25060 KB Ok