Cod sursa(job #2329770)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 27 ianuarie 2019 13:58:51
Problema Zone Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.5 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

const int NMAX = 520;

struct Zone {
  int l1, c1, l2, c2;
  bool operator < (const Zone &other) const {
    if (l1 != other.l1) return l1 > other.l1;
    if (c1 != other.c1) return c1 > other.c1;
    if (l2 != other.l2) return l2 > other.l2;
    return (l1 + c1 + l2 + c2) > (other.l1 + other.c1 + other.l2 + other.c2);
  }
};

int n;
ll sum1, sum2, sum4;
int used[15];
ll s[15];
ll sum[NMAX][NMAX];
priority_queue <Zone> ans;

ll getSum (int up_row, int left_col, int bot_row, int right_col) {
  return sum[bot_row][right_col] - sum[up_row - 1][right_col] - sum[bot_row][left_col - 1] + sum[up_row - 1][left_col - 1];
}

int binSearchCol (ll curr_sum, int lo, int hi, int up_row, int bot_row) {
  int left_col = lo;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    ll s = getSum (up_row, left_col, bot_row, mid);
    if (s == curr_sum) {
      return mid;
    }
    if (s < curr_sum) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return -1;
}

int binSearchRow (ll curr_sum, int lo, int hi, int left_col, int right_col) {
  int up_row = lo;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    ll s = getSum (up_row, left_col, mid, right_col);
    if (s == curr_sum) {
      return mid;
    }
    if (s < curr_sum) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return -1;
}

void makeAvailable() {
  for (int i = 1; i <= 9; ++i) {
    if (used[i] != 1 && used[i] != 2 && used[i] != 4) used[i] = 0;
  }
}

bool notAvailable (ll sum) {
  for (int i = 1; i <= 9; ++i) {
    if (s[i] == sum && !used[i]) {
      used[i] = 10;
      return false;
    }
  }
  makeAvailable();
  return true;
}

bool checkRemZones (int l1, int c1, int l2, int c2) {
  ll sum = 0;
  sum = getSum (l1 + 1, c1 + 1, l2, c2);
  if (notAvailable (sum)) {
    makeAvailable();
    return false;
  }

  sum = getSum (l1 + 1, c2 + 1, l2, n);

  if (notAvailable (sum)) {
    makeAvailable();
    return false;
  }

  sum = getSum (l2 + 1, 1, n, c1);

  if (notAvailable (sum)) {
    makeAvailable();
    return false;
  }

  sum = getSum (l2 + 1, c1 + 1, n, c2);

  if (notAvailable (sum)) {
    makeAvailable();
    return false;
  }

  sum = getSum (l2 + 1, c2 + 1, n, n);

  if (notAvailable (sum)) {
    makeAvailable();
    return false;
  }

  return true;
}

void check() {
  for (int l1 = 1; l1 <= n - 2; ++l1) {
    int c1 = binSearchCol (sum1, 1, n - 2, 1, l1);
    if (c1 == -1) continue;

    int c2 = binSearchCol (sum2, c1 + 1, n - 1, 1, l1);
    if (c2 == -1) continue;

    if (notAvailable (getSum (1, c2 + 1, l1, n))) continue;

    int l2 = binSearchRow (sum4, l1 + 1, n - 1, 1, c1);
    if (l2 == -1) {
      makeAvailable();
      continue;
    }
//    fprintf (stderr, "%d %d %d %d\n", l1, l2, c1, c2);

    if (checkRemZones (l1, c1, l2, c2)) {
      ans.push ({l1, c1, l2, c2});
      fprintf (stderr, "%d %d %d %d\n", l1, c1, l2, c2);
      while (ans.size() > 1) {
        ans.pop();
      }
      return;
    }
    makeAvailable();
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  freopen ("zone.in", "r", stdin);
  freopen ("zone.out", "w", stdout);

  scanf ("%d", &n);
  for (int i = 1; i <= 9; ++i) {
    scanf ("%lld", &s[i]);
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      scanf ("%lld", &sum[i][j]);
      sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
  }

  sort (s + 1, s + 9 + 1);
  for (int i = 1; i <= 9; ++i) {
    used[i] = 1;
    sum1 = s[i];
    for (int j = 1; j <= 9; ++j) {
      if (used[j]) continue;
      used[j] = 2;
      sum2 = s[j];
      for (int k = 1; k <= 9; ++k) {
        if (used[k]) continue;
        used[k] = 4;
        sum4 = s[k];
        check();
        used[k] = 0;
      }
      used[j] = 0;
    }
    used[i] = 0;
  }

  Zone res = ans.top();
  printf ("%d %d %d %d\n", res.l1, res.l2, res.c1, res.c2);

  fclose (stdin);
  fclose (stdout);

#ifdef LOCAL_DEFINE
  fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}