Pagini recente » Cod sursa (job #2148832) | Cod sursa (job #2217484) | Cod sursa (job #2184688) | Cod sursa (job #2868317) | Cod sursa (job #2357970)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
long long a[513][513],b[513][513];
int l1,c1,l2,c2,i,j,k1,k2,k3,k4,ok,v[10],viz[10],n,m,fr[11];
int cautbin(long long S){
int st=1,dr=m,mid;
while(st<=dr){
mid=(st+dr)/2;
if(v[mid]<S)
st=mid+1;
else if(v[mid]>S)
dr=mid-1;
else
return mid;
}
return -1;
}
int cautc(long long S,int x,int st,int dr){
int mid;
while(st<=dr){
mid=(st+dr)/2;
if(b[x][mid]==S)
return mid;
else if(b[x][mid]>S)
dr=mid-1;
else
st=mid+1;
}
return -1;
}
int valid(){
for(int h=1;h<=m;h++)
viz[h]=0;
viz[k4]=viz[k3]=viz[k2]=viz[k1]=1;
int k5=cautbin(b[l2][c2]-b[l2][c1]-b[l1][c2]+b[l1][c1]);
int k6=cautbin(b[l2][n]-b[l2][c2]-b[l1][n]+b[l1][c2]);
int k7=cautbin(b[n][c1]-b[l2][c1]);
int k8=cautbin(b[n][c2]-b[n][c1]-b[l2][c2]+b[l2][c1]);
int k9=cautbin(b[n][n]-b[l2][n]-b[n][c2]+b[l2][c2]);
if(k5==-1||k6==-1||k7==-1||k8==-1||k9==-1)
return 0;
viz[k5]++;
viz[k6]++;
viz[k7]++;
viz[k8]++;
viz[k9]++;
for(int h=1;h<=m;h++)
if(viz[h]>fr[h])
return 0;
return 1;
}
int cautl(long long S,int y,int st,int dr){
int mid;
while(st<=dr){
mid=(st+dr)/2;
if(b[mid][y]==S)
return mid;
else if(b[mid][y]>S)
dr=mid-1;
else
st=mid+1;
}
return -1;
}
int main ()
{ f>>n;
for(i=1;i<=9;i++)
f>>v[i];
sort(v+1,v+10);
m=0;
int nr=1;
for(i=1;i<=8;i++)
if(v[i]!=v[i+1]){
fr[++m]=nr;
v[m]=v[i];
nr=1;
}
else
nr++;
if(v[i]!=v[i+1]){
fr[++m]=nr;
v[m]=v[i];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
f>>a[i][j];
b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
for(l1=1;l1<=n-2;l1++){
for(k1=1;k1<=m;k1++){
c1=cautc(v[k1],l1,1,n-2);
if(c1!=-1)
for(k2=1;k2<=m;k2++){
c2=cautc(v[k1]+v[k2],l1,c1+1,n-1);
if(c2!=-1){
ok=0;
for(k3=1;k3<=m;k3++){
if(b[l1][n]==v[k1]+v[k2]+v[k3]){
ok=1;
break;
}
}
}
if(ok==1){
for(k4=1;k4<=m;k4++){
l2=cautl(v[k1]+v[k4],c1,l1+1,n-1);
if(l2!=-1){
if(valid()==1){
g<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
return 0;
}
}
}
}
}
}
}
return 0;
}