Cod sursa(job #1377636)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 5 martie 2015 23:16:30
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.76 kb
#include <fstream>
#include <algorithm>
#define DIM 512
using namespace std;

ifstream fin ("zone.in" );
ofstream fout("zone.out");

int N, k, ii, jj, iii, i, j, l1, l2, c1, c2, p, u, mid;
long long A[DIM][DIM], D[DIM][DIM], V[10], W[10], ok;

long long Sigma(int x, int y, int z, int t){
    return D[z][t] - D[x-1][t] - D[z][y-1] + D[x-1][y-1];
}

void SetUp(){
     fin >> N;
     for(i = 1; i <= 9; i ++)
          fin >> V[i];
     sort(V + 1, V + 10);
     l1 = l2 = c1 = c2 = DIM * 2;
     return;
}

void Partial(){
     for(i = 1; i <= N; i ++)
          for(j = 1; j <= N; j ++)
               fin >> A[i][j];
     for(i = 1; i <= N; i ++)
          for(j = 1; j <= N; j ++)
               D[i][j] = A[i][j] + D[i-1][j] + D[i][j-1] - D[i-1][j-1];
     return;
}

void BinarySearch1(){
     p = 1; u = 9;
     while(p <= u){
          mid = (p + u) / 2;
          if(V[mid] == Sigma(1, 1, i, j))
               break;
          if(V[mid] > Sigma(1, 1, i, j))
              u = mid - 1;
          else
              p = mid + 1;
     }
     return;
}

void BinarySearch2(){
     p = 1; u = 9;
     while(p <= u){
          mid = (p + u) / 2;
          if(V[mid] == Sigma(i + 1, 1, ii, j))
               break;
          if(V[mid] > Sigma(i + 1, 1, ii, j))
               u = mid - 1;
          else
            p = mid + 1;
     }
     return;
}

void Sigmas(){
     W[1] = Sigma(1, 1, i, j);
     W[2] = Sigma(i + 1, 1, ii, j);
     W[3] = Sigma(ii + 1, 1, N, j);
     W[4] = Sigma(1, j + 1, i, jj);
     W[5] = Sigma(i + 1, j + 1, ii, jj);
     W[6] = Sigma(ii + 1, j + 1, N, jj);
     W[7] = Sigma(1, jj + 1, i, N);
     W[8] = Sigma(i + 1 , jj + 1, ii, N);
     W[9] = Sigma(ii + 1, jj + 1, N, N);
     return;
}

void Disaster(){
     for(i = 1; i < N - 1; i ++)
          for(j = 1; j < N - 1; j ++){
               BinarySearch1();
               if(p <= u)
                    for(ii = i + 1; ii < N; ii ++){
                         BinarySearch2();
                         if(p <= u)
                              for(jj = j + 1; jj < N; jj ++){
                                   Sigmas();
                                   sort(W + 1, W + 10);
                                   ok = 1;
                                   for(int iii = 1; iii <= 9; iii ++)
                                        if(V[iii] != W[iii]){
                                             ok = 0;
                                             break;
                                        }
                                   if(ok == 1){
                                        if(i < l1){
                                             l1 = i;
                                             c1 = j;
                                             l2 = ii;
                                             c2 = jj;
                                        }
                                        else
                                             if(i == l1)
                                                  if(c1 > j){
                                                       l1 = i;
                                                       c1 = j;
                                                       l2 = ii;
                                                       c2 = jj;
                                                  }
                                                  else
                                                       if(c1 == j)
                                                            if(l2 > ii){
                                                                 l1 = i;
                                                                 c1 = j;
                                                                 l2 = ii;
                                                                 c2 = jj;
                                                            }
                                                            else
                                                                 if(l2 == ii)
                                                                      if(c2 > jj){
                                                                           l1 = i;
                                                                           c1 = j;
                                                                           l2 = ii;
                                                                           c2 = jj;
                                                                      }
                                   }
                    }
               }
          }
     return;
}

int main(){
     SetUp();
     Partial();
     Disaster();
     fout << l1 << " " << l2 << " " << c1 << " " << c2 << "\n";
     return 0;
}