Cod sursa(job #1937705)
Utilizator | Data | 24 martie 2017 10:09:41 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.29 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
int a[513][513];
long long v[10];
long long r[10];
long long suma(int l1,int c1,int l2,int c2){
return 1LL*a[l2][c2]-a[l1-1][c2]-a[l2][c1-1]+a[l1-1][c1-1];
}
int exista(int nr){
int st=1,dr=9,m,poz=0;
while(st<=dr){
m=(st+dr)/2;
if(v[m]>=nr){
dr=m-1;
poz=m;
}else
st=m+1;
}
if(v[poz]==nr)
return 1;
return 0;
}
int main(){
int n,i,j,ind,l1,c1,st,dr,m,s,l2,c2,k;
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=9;i++)
scanf("%lld",&v[i]);
sort(v+1,v+10);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&a[i][j]);
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
ind=1;
for(l1=1;l1<=n-2;l1++)
for(c1=1;c1<=n-2;c1++){
while(v[ind]<a[l1][c1])
ind++;
if(v[ind]==a[l1][c1]){
for(i=1;i<=9;i++){
if(i!=ind){
st=l1+1;
dr=n;
while(st<=dr){
m=(st+dr)/2;
s=suma(l1+1,1,m,c1);
if(s>=v[i]){
dr=m-1;
l2=m;
}else
st=m+1;
}
if(suma(l1+1,1,l2,c1)==v[i]&&exista(suma(l2+1,1,n,c1))){
for(j=1;j<=9;j++)
if(j!=i&&j!=ind){
st=c1+1;
dr=n;
while(st<=dr){
m=(st+dr)/2;
s=suma(1,c1+1,l1,m);
if(s>=v[j]){
dr=m-1;
c2=m;
}else
st=m+1;
}
if(suma(1,c1+1,l1,c2)==v[j]&&exista(suma(1,c2+1,l1,n))){
r[1]=suma(1,1,l1,c1);
r[2]=suma(1,c1+1,l1,c2);
r[3]=suma(1,c2+1,l1,n);
r[4]=suma(l1+1,1,l2,c1);
r[5]=suma(l1+1,c1+1,l2,c2);
r[6]=suma(l1+1,c2+1,l2,n);
r[7]=suma(l2+1,1,n,c1);
r[8]=suma(l2+1,c1+1,n,c2);
r[9]=suma(l2+1,c2+1,n,n);
sort(r+1,r+10);
for(k=1;k<=9;k++)
if(v[k]!=r[k])
k=11;
if(k==10){
printf("%d %d %d %d",l1,l2,c1,c2);
return 0;
}
}
}
}
}
}
}
}
return 0;
}