Cod sursa(job #1159211)
Utilizator | Data | 29 martie 2014 13:44:46 | |
---|---|---|---|
Problema | Zone | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.36 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
long long i, ss, o, n, p, k, ok, u, d, f, c1, l1, c2, l2, j, w[45], v[45], a[520][520], b[520][520];
int main()
{
freopen("zone.in", "r", stdin);
freopen("zone.out", "w", stdout);
scanf("%lld", &n);
for(i=1;i<=9;i++)
scanf("%lld", &w[i]);
sort(w+1,w+10);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%lld", &a[i][j]);
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
}
for(i=1;i<=n;i++)
{
l1=i;
for(j=1;j<=9;j++)
{
p=1;
c1=0;
u=n;
ss=w[j];
while(p<=u)
{
k=(p+u)/2;
if(b[l1][k]==ss)
{
c1=k;
break;
}
else if(b[l1][k]>ss) u=k-1;
else p=k+1;
}
for(o=1;o<=9;o++)
{
if(o!=j)
{
l2=0;
p=1;
u=n;
ss=w[o];
while(p<=u)
{
k=(p+u)/2;
if(b[k][c1]-b[l1][c1]==ss)
{
l2=k;
break;
}
else if(b[k][c1]-b[l1][c1]>ss) u=k-1;
else p=k+1;
}
for(f=1;f<=9;f++)
{
if(f!=o&&f!=j)
{
p=1;
u=n;
ss=w[f];
while(p<=u)
{
k=(p+u)/2;
if(b[l2][k]-b[l2][c1]-b[l1][k]+b[l1][c1]==ss)
{
c2=k;
break;
}
else if(b[l2][k]-b[l2][c1]-b[l1][k]+b[l1][c1]>ss) u=k-1;
else p=k+1;
}
v[1]=b[l1][c1];
v[2]=b[l2][c1]-b[l1][c1];
v[3]=b[l2][c2]-b[l2][c1]-b[l1][c2]+b[l1][c1];
v[4]=b[l1][c2]-b[l1][c1];
v[5]=b[l1][n]-b[l1][c2];
v[6]=b[l2][n]-b[l2][c2]-b[l1][n]+b[l1][l2];
v[7]=b[n][c1]-b[l2][c1];
v[8]=b[n][c2]-b[n][c1]-b[l2][c2]+b[l2][c1];
v[9]=b[n][n]-b[n][c2]-b[l2][n]+b[l2][c2];
sort(v+1,v+10);
ok=1;
for(d=1;d<=9;d++)
if(v[d]!=w[d])
{
ok=0;
break;
}
if(ok==1)
{
printf("%lld %lld %lld %lld", l1, l2, c1, c2);
return 0;
}}
}
}
}
}
}
return 0;
}