Cod sursa(job #1377636)
Utilizator | 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;
}