Submission #1403734

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

const int inf = 1000;

int main(void){
  int n;
  cin >> n;
  VI a(n);
  vector<PI> pool;
  REP(i, 0, n) {
    cin >> a[i];
    pool.push_back(PI(a[i], i));
  }
  sort(pool.begin(), pool.end());
  int h, w;
  cin >> h >> w;
  vector<VI> b(h, VI(w));
  vector<PI> mi(n, PI(inf, inf)), ma(n, PI(-inf, -inf));
  REP(i, 0, h) {
    REP(j, 0, w) {
      cin >> b[i][j];
      int c = b[i][j];
      mi[c].first = min(mi[c].first, i);
      mi[c].second = min(mi[c].second, j);
      ma[c].first = max(ma[c].first, i);
      ma[c].second = max(ma[c].second, j);
    }
  }
  assert (n <= 10);
  // Try all possibilities, O(n!)
  VI perm(n);
  REP(i, 0, n) {
    perm[i] = i;
  }
  bool ok = false;
  do {
    // This permutation is valid?
    bool valid = true;
    if (not valid) {
      continue;
    }
    vector<VI> board(h, VI(w, -1));
    vector<VI> order(h, VI(w, -1));
    REP(i, 0, n) {
      int p = perm[i];
      int c = pool[i].second;
      if (not valid) {
	break;
      }
      REP(j, mi[p].first, ma[p].first + 1) {
	if (not valid) {
	  break;
	}
	REP(k, mi[p].second, ma[p].second + 1) {
	  int oldc = order[j][k];
	  if (oldc >= 0 && a[oldc] == a[c]) {
	    valid = false;
	    break;
	  }
	  board[j][k] = p;
	  order[j][k] = c;
	}
      }
    }
    if (0) {
      cerr << "board:" << endl;
      REP(k, 0, board.size()) {
	REP(l, 0, board[0].size()) {
	  cerr << " " << board[k][l];
	}
	cerr << endl;
      }
    }
    if (not valid) {
      continue;
    }
    if (board == b) {
      ok = true;
    }
  } while (next_permutation(perm.begin(), perm.end()) && not ok);
  cout << (ok ? 1 : 0) << endl;
}

Submission Info

Judge Result