Pagini recente » Cod sursa (job #2153008) | Cod sursa (job #2913029) | Cod sursa (job #991661) | Cod sursa (job #1314339) | Cod sursa (job #2197761)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("zone.in");
ofstream out ("zone.out");
long long v[520][520],s[520][520],val[11],vv[11],n;
long long col (long long poz, long long i, long long j)
{
long long pas=1<<10,k=poz;
while(pas)
{
if(k+pas<=n && s[i][k+pas]-s[i][poz-1]<=val[j])
k+=pas;
pas>>=1;
}
if(s[i][k]-s[i][poz-1]==val[j])
return k;
return -1;
}
long long lin (long long poz, long long i, long long j)
{
long long pas=1<<10,k=poz;
while(pas)
{
if(k+pas<=n && s[k+pas][i]-s[poz-1][i]<=val[j])
k+=pas;
pas>>=1;
}
if(s[k][i]-s[poz-1][i]==val[j])
return k;
return -1;
}
bool verif (long long l1, long long l2, long long c1, long long c2)
{
vv[1]=s[l1][c1];
vv[2]=s[l1][c2]-vv[1];
vv[3]=s[l1][n]-s[l1][c2];
vv[4]=s[l2][c1]-vv[1];
vv[5]=s[l2][c2]-s[l1][c2]-s[l2][c1]+vv[1];
vv[6]=s[l2][n]-s[l2][c2]-vv[3];
vv[7]=s[n][c1]-s[l2][c1];
vv[8]=s[n][c2]-s[l2][c2]-vv[7];
vv[9]=s[n][n]-s[l2][n]-s[n][c2]+s[l2][c2];
sort(vv+1,vv+10);
for(long long i=1;i<=9;i++)
if(vv[i]!=val[i])
return false;
return true;
}
int main()
{
long long i,j,a,b,c,jj,jjj;
in>>n;
for(i=1;i<=9;i++)
in>>val[i];
sort(val+1,val+10);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
in>>v[i][j];
s[i][j]=v[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=9;j++)
{
a=col(1,i,j);
if(a==-1)
continue;
for(jj=1;jj<=9;jj++)
{
if(jj!=j)
{
b=col(a+1,i,jj);
if(b==-1)
continue;
for(jjj=1;jjj<=9;jjj++)
{
if(jjj!=jj && jjj!=j)
{
c=lin(i+1,a,jjj);
if(c==-1)
continue;
if(verif(i,c,a,b))
{
out<<i<<' '<<c<<' '<<a<<' '<<b;
i=n+1;
j=jj=jjj=1000;
break;
}
}
}
}
}
}
}
return 0;
}