Cod sursa(job #2197624)

Utilizator lucametehauDart Monkey lucametehau Data 22 aprilie 2018 16:38:19
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <fstream>

using namespace std;

ifstream cin ("zone.in");
ofstream cout ("zone.out");

const int nmax = 512;

int n;
int sl1, sl2, sc1, sc2;

long long sum[10];
long long s[1 + nmax][1 + nmax];
bool taken[10];

int searchCol(int line, int l, int r, long long val) {
  int st = l, dr = r, mid;
  while(st <= dr) {
    mid = (st + dr) / 2;
    if(s[line][mid] - s[line][l - 1] < val)
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return st;
}

int searchLin(int column, int l, int r, long long val) {
  int st = l, dr = r, mid;
  while(st <= dr) {
    mid = (st + dr) / 2;
    if(s[mid][column] - s[l - 1][column] < val)
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return st;
}

bool isSolution(long long suma) {
  for(int i = 1; i <= 9; i++) {
    if(suma == sum[i] && !taken[i]) {
      taken[i] = 1;
      return 1;
    }
  }
  return 0;
}

int main() {
  cin >> n;
  for(int i = 1; i <= 9; i++)
    cin >> sum[i];
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++) {
      cin >> s[i][j];
      s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1];
    }
  sl1 = sl2 = sc1 = sc2 = nmax;
  for(int z1 = 1; z1 <= 9; z1++) {
    for(int i = 1; i < n - 1; i++) {
      int c1 = searchCol(i, 1, n - 2, sum[z1]);
      if(s[i][c1] != sum[z1])
        continue;
      for(int z2 = 1; z2 <= 9; z2++) {
        if(z2 == z1)
          continue;
        int c2 = searchCol(i, c1 + 1, n - 1, sum[z2]);
        if(s[i][c2] - s[i][c1] != sum[z2])
          continue;
        for(int z3 = 1; z3 <= 9; z3++) {
          if(z3 == z1 || z3 == z2)
            continue;
          int j = searchLin(c1, i + 1, n - 1, sum[z3]);
          if(s[j][c1] - s[i][c1] != sum[z3])
            continue;
          for(int k = 1; k <= 9; k++)
            taken[k] = 0;
          if(!isSolution(s[i][n] - s[i][c2]))
            continue;
          if(!isSolution(s[j][c2] - s[j][c1] - s[i][c2] + s[i][c1]))
            continue;
          if(!isSolution(s[j][n] - s[j][c2] - s[i][n] + s[i][c2]))
            continue;
          if(!isSolution(s[n][c1] - s[j][c1]))
            continue;
          if(!isSolution(s[n][c2] - s[n][c1] - s[j][c2] + s[j][c1]))
            continue;
          if(!isSolution(s[n][n] - s[n][c2] - s[j][n] + s[j][c2]))
            continue;
          if(i == sl1) {
            if(j == sl2) {
              if(c1 == sc1) {
                if(c2 < sc2)
                  sc2 = c2;
              } else if(c1 < sc1) {
                sc1 = c1;
                sc2 = c2;
              }
            } else if(j < sl2) {
              sl2 = j;
              sc1 = c1;
              sc2 = c2;
            }
          } else if(i < sl1) {
            sl1 = i;
            sl2 = j;
            sc1 = c1;
            sc2 = c2;
          }
        }
      }
    }
  }
  cout << sl1 << " " << sl2 << " " << sc1 << " " << sc2;
  return 0;
}