Cod sursa(job #1258849)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 9 noiembrie 2014 15:01:12
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <map>

int a[550][550];
long long sum[550][550];
int n;
int l1, c1, l2, c2;
long long v[9];

inline long long get_sum(int i1, int i2, int j1, int j2) {
  return sum[i2][j2] - sum[i1 - 1][j2] - sum[i2][j1 - 1] + sum[i1 - 1][j1 - 1];
}

bool operator== (const std::map<long long, int>& left,
                 const std::map<long long, int>& right) {
  typename std::map<long long, int>::const_iterator itl = left.begin();
  typename std::map<long long, int>::const_iterator itr = right.begin();
  while (itl != left.end() && itl != right.end()) {
    if (itl->second == 0) {
      itl++;
      continue;
    }

    if (itr->second == 0) {
      itr++;
      continue;
    }

    if (itl->first != itr->first || itl->second != itr->second) {
      return false;
    }
    itl++;
    itr++;
  }

  while (itl != left.end() && itl->second == 0) {
    itl++;
  }

  while (itr != right.end() && itr->second == 0) {
    itr++;
  }

  if (itl != left.end() || itr != right.end()) {
    return false;
  }

  return true;
}

void solve() {
  // Count vectors.
  std::map<long long, int> cts;
  for (int i = 0; i < 9; ++i) {
    cts[v[i]]++;
  }

  // The backtracking.
  for (l1 = 1; l1 <= n - 2; ++l1) {
    for (c1 = 1; c1 <= n - 2; ++c1) {
      int s1 = get_sum(1, l1, 1,  c1);
      if (cts.count(s1) && cts[s1]) {
        cts[s1]--;
        for (l2 = l1 + 1; l2 <= n - 1; ++l2) {
          long long s2 = get_sum(l1 + 1, l2, 1, c1);
          long long s3 = get_sum(l2 + 1, n, 1, c1);
          if (cts.count(s2) && cts[s2]) {
            cts[s2]--;
            if (cts.count(s3) && cts[s3]) {
              cts[s3]--;
              for (c2 = c1 + 1; c2 <= n - 1; ++c2) {
                std::map<long long, int> os;
                os[get_sum(1, l1, c1 + 1, c2)]++;
                os[get_sum(l1 + 1, l2, c1 + 1, c2)]++;
                os[get_sum(l2 + 1, n, c1 + 1, c2)]++;
                os[get_sum(1, l1, c2 + 1, n)]++;
                os[get_sum(l1 + 1, l2, c2 + 1, n)]++;
                os[get_sum(l2 + 1, n, c2 + 1, n)]++;
                if (os == cts) {
                  return;
                }
              }
              cts[s3]++;
            }
            cts[s2]++;
          }
        }
        cts[s1]++;
      }
    }
  }
}

int main()
{
  std::ifstream in("zone.in");
  std::ofstream out("zone.out");

  in >> n;
  for (int i = 0; i < 9; ++i) {
    in >> v[i];
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      in >> a[i][j];
      sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
  }

  solve();

  out << l1 << " " << l2 << " " << c1 << " " << c2 << std::endl;

  in.close();
  out.close();

  return 0;
}