Pagini recente » Cod sursa (job #2840947) | Cod sursa (job #1558598) | Cod sursa (job #2037480) | Cod sursa (job #2921546) | Cod sursa (job #2358331)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
long long a[515][515],v[10],s[10];
bool viz[10];
int x,n;
int cautbin_lin2(long long val, int l1, int c1)
{
int st=l1,dr=n-1;
while(st<=dr)
{
int mid=(st+dr)/2;
long long nr=a[mid][c1]-a[l1][c1];
if(nr==val)
return mid;
else if(nr>val)
dr=mid-1;
else
st=mid+1;
}
return -1;
}
int cautbin_col(int l, int st, int dr, long long val, int colst)
{
while(st<=dr)
{
int mid=(st+dr)/2;
if(val==a[l][mid]-a[l][colst])
return mid;
else if(a[l][mid]-a[l][colst]>val)
dr=mid-1;
else if(a[l][mid]-a[l][colst]<val)
st=mid+1;
}
return -1;
}
bool verif(int l1, int l2, int c1, int c2)
{
long long aux[10];
for(int i=1;i<=4;i++)
aux[i]=v[i];
aux[5]=a[l2][c2]+a[l1][c1]-a[l1][c2]-a[l2][c1];
aux[6]=a[l2][n]+a[l1][c2]-a[l1][n]-a[l2][c2];
aux[7]=a[n][c1]-a[l2][c1];
aux[8]=a[n][c2]+a[l2][c1]-a[l2][c2]-a[n][c1];
aux[9]=a[n][n]+a[l2][c2]-a[l2][n]-a[n][c2];
sort(aux+1,aux+10);
for(int i=1;i<=9;i++)
if(aux[i]!=s[i])
return 0;
return 1;
}
int main()
{
fin>>n;
for(int i=1;i<=9;i++)
fin>>s[i];
sort(s+1,s+10);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
fin>>x;
a[i][j]=x+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
for(int l1=1;l1<=n-2;l1++)
for(int s1=1;s1<=9;s1++)
if(!viz[s1])
{
int c1=cautbin_col(l1,1,n-2,s[s1],1);
if(c1!=-1)
{
viz[s1]=1;
v[1]=a[l1][c1];
for(int s2=1;s2<=9;s2++)
if(!viz[s2])
{
viz[s2]=1;
int c2=cautbin_col(l1,c1+1,n-1,s[s2],c1);
if(c2!=-1)
{
viz[s2]=1;
v[2]=a[l1][c2]-a[l1][c1];
int sum3=a[l1][n]-a[l1][c2];
for(int s3=1;s3<=9;s3++)
if(!viz[s3]&&s[s3]==sum3)
{
viz[s3]=1;
v[3]=sum3;
for(int s4=1;s4<=9;s4++)
if(!viz[s4])
{
int l2=cautbin_lin2(s[s4],l1,c1);
if(l2!=-1)
{
v[4]=s[s4];
if(verif(l1,l2,c1,c2))
{
fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
return 0;
}
}
}
viz[s3]=0;
}
}
viz[s2]=0;
}
}
viz[s1]=0;
}
return 0;
}