Pagini recente » Cod sursa (job #484051) | Cod sursa (job #330971) | Cod sursa (job #132327) | Cod sursa (job #1897428) | Cod sursa (job #2357482)
#include <fstream>
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
long long a[512][512];
int cautbin(long long S){
int st=1,dr=n;
while(st<=dr){
mid=(st+dr)/2;
if(v[mid]<S)
st=mid+1;
else if(v[mid]>S)
st=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(){
viz[k4]=viz[k3]=viz[k2]=viz[k1]=1;
k5=cautbin(b[l2][c2]-b[l2][c1]-b[l1][c2]+b[l1][c1]);
k6=cautbin(b[l2][n]-b[l2][c2]-b[l1][n]+b[l1][c2]);
k7=cautbin(b[n][c1]-b[l2][c1]);
k8=cautbin(b[n][c2]-b[n][c1]-b[l2][c2]+b[l2][c1]);
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[k7]++;
viz[k8]++;
viz[k9]++;
for(int i=1;i<=9;i++)
if(viz[i]>=2)
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];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
f>>a[i][j];
b[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
sort(v+1,v+10);
for(l1=2;l1<=n-2;l1++){
for(k1=1;k1<=9;k1++){
c1=cautc(v[k1],l1,1,n-2);
if(c1!=-1)
for(k2=1;k2<=9;k2++){
if(k2!=k1){
c2=cautc(v[k1]+v[k2],l1,c1+1,n-1);
if(c2!=-1){
for(k3=1;k3<=9;k3++){
ok=0;
if(k3!=k2&&k3!=k1)
if(b[l1][n]==v[k1]+v[k2]+v[k3])
ok=1;
}
}
if(ok==1){
for(k4=1;k4<=9;k4++){
if(k4!=k3&&k4!=k2&&k4!=k1){
l2=cautl(v[k1]+v[k4],c1,l1+1,n-1);
if(l2!=-1){
if(valid()==1){
g<<l1<<' '<<c1<<' '<<l2<<' '<<c2;
}
}
}
}
}
}
}
}
}
return 0;
}