Pagini recente » Cod sursa (job #1398552) | Cod sursa (job #2488736) | Cod sursa (job #2257933) | Cod sursa (job #605303) | Cod sursa (job #2358007)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
long long a[513][513],b[513][513],v[11];
int l1,c1,l2,c2,i,j,k1,k2,k3,k4,ok,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;
}
void resetViz(int poz){
for(int h=1;h<=m;h++)
viz[h]=fr[h];
if(poz>=1)
viz[k1]--;
if(poz>=2)
viz[k2]--;
if(poz>=3)
viz[k3]--;
}
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++){
resetViz(0);
c1=cautc(v[k1],l1,1,n-2);
if(c1!=-1){
viz[k1]--;
for(k2=1;k2<=m;k2++){
resetViz(1);
c2=cautc(v[k1]+v[k2],l1,c1+1,n-1);
if(c2!=-1&&viz[k2]>=1){
viz[k2]--;
ok=0;
for(k3=1;k3<=m;k3++){
if(b[l1][n]==v[k1]+v[k2]+v[k3]&&viz[k3]>=1){
ok=1;
break;
}
}
viz[k3]--;
}
if(ok==1){
for(k4=1;k4<=m;k4++){
resetViz(3);
l2=cautl(v[k1]+v[k4],c1,l1+1,n-1);
if(l2!=-1&&viz[k4]>=1){
if(valid()==1){
g<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
return 0;
}
}
}
}
}
}
}
}
return 0;
}