Euler 185

gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <complex>
#include <cassert>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <queue>
#include <bitset>

using namespace std;

typedef unsigned long long ullong;
typedef long long llong;
typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
    it != adj[v].end(); ++it)

const int MAX_N = 24;
const int MAX_M = 64;

int n;
int m;

int seq[MAX_N];
bool mat[MAX_N][10];
int poss[MAX_N];
char lines[MAX_M][MAX_N];
int n_corr[MAX_N];
ii perm[MAX_M];

inline uint32_t next_bit_perm(uint32_t v) {
  uint32_t t = v | (v - 1);
  return (t+1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
}

bool recurse(int idx) {
#ifndef NDEBUG
  printf("> R(%d)\n", idx);
#endif
  if (m == idx) {
    printf("Yey\n");
    for (int i = 0; i < n; ++i) {
      printf("%d ", i);
      for (int j = 0; j < 10; ++j) {
        if (mat[i][j]) printf("%d ", j);
      }
      puts("");
    }
    /* if we reached here, we must be right */
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < 10; ++j) {
        if (mat[i][j]) {
          seq[i] = j;
          break;
        }
      }
    }
    return true;
  }

  int p = perm[idx].second;
  int nc = n_corr[p];

  if (nc == 0) {
    for (int i = 0; i < n; ++i) {
      int x = lines[p][i];
      if (mat[i][x] && poss[i] == 1) {
        return false;
      }
      poss[i] -= mat[i][x];
      mat[i][x] = 0;
    }
    if (recurse(idx+1)) {
      return true;
    }
    return false;
  }

  uint32_t start = 0;
  uint32_t end = 0;
  for (int i = 0; i < nc; ++i) {
    start |= 1 << i;
    end |= 1 << (n - 1 - i);
  }
  end = next_bit_perm(end);

  bool old_mat[MAX_N][10];
  int old_poss[MAX_N];
  memcpy(old_mat, mat, sizeof(mat));
  memcpy(old_poss, poss, sizeof(poss));
  for (uint32_t mask = start; mask != end; mask = next_bit_perm(mask)) {
    bool good = true;
    /* bit set at index i means consider that index correct */
#ifndef NDEBUG
    printf(">> %d ", nc);
    for (int i = 0; i < n; ++i) {
      printf("%d", (mask >> i) & 1);
    }
    puts("");
    int cnt = 0;
#endif
    for (int i = 0; i < n; ++i) {
      int x = lines[p][i];
      if ((mask >> i) & 1) {
#ifndef NDEBUG
        ++cnt;
#endif
        if (!old_mat[i][x]) {
          /* tried to consider i correct, but resulted in contradiction */
          good = false;
          break;
        }
      } else {
        if (old_mat[i][x] && old_poss[i] == 1) {
          /* we are considering the last possible value wrong, which cannot be */
          good = false;
          break;
        }
      }
    }
    if (!good) continue;
    assert(cnt == nc);

    memcpy(mat, old_mat, sizeof(mat));
    memcpy(poss, old_poss, sizeof(poss));

    for (int i = 0; i < n; ++i) {
      int x = lines[p][i];
      if ((mask >> i) & 1) {
        /* now set all other possibilities to false */
        memset(mat[i], 0, sizeof(mat[i]));
        mat[i][x] = 1;
        poss[i] = 1;
      } else {
        /* this index is considered wrong */
        /* Note that we used a branchless way to do this :D */
        poss[i] -= mat[i][x];
        mat[i][x] = 0;
      }
    }

    if (recurse(idx+1)) {
      return true;
    }
  }

  return false;
}

int main() {
  for (int i = 0; i < MAX_N; ++i) for (int j = 0; j < 10; ++j) mat[i][j] = 1;
  for (int i = 0; i < MAX_N; ++i) poss[i] = 10;
  
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%s", lines[i]);
    for (int j = 0; j < n; ++j) {
      lines[i][j] -= '0';
    }
    scanf("%d", &n_corr[i]);
  }

  for (int i = 0; i < m; ++i) {
    perm[i] = make_pair(n_corr[i], i);
  }
  sort(perm, perm+m);

  for (int i = 0; i < m; ++i){
    int p = perm[i].second;
    printf("%d ", p);
    for (int j = 0; j < n; ++j) {
      printf("%d", lines[p][j]);
    }
    printf(" %d\n", n_corr[p]);
  }

  bool rv = recurse(0);
  printf("%d\n", rv);

  for (int i = 0; i < n; ++i) {
    printf("%d", seq[i]);
  }
  puts("");

  return 0;
}