Submission #346689

#	Time	Username	Problem	Language	Result	Execution time	Memory
346689		milleniumEeee	"The Lyuboyn" code (IZhO19_lyuboyn)	C++17	100 / 100	658 ms	49120 KiB

lyuboyn

#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
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 31 / 31
• Subtask 8: 17 / 17