Pagini recente » Cod sursa (job #314640) | Cod sursa (job #456725) | Cod sursa (job #1377846) | Cod sursa (job #2023490) | Cod sursa (job #2071050)
#include <cstdio>
#include <bitset>
using namespace std;
long long s[9],a[513][513];
bitset <9> f;
int verif (long long sum){
int i;
for (i=1;i<=9;i++){
if (s[i]==sum && f[i]==0){
f[i]=1;
return 1;
}
}
return 0;
}
int main()
{
FILE *fin=fopen ("zone.in","r");
FILE *fout=fopen ("zone.out","w");
int n,i,j,s1,s2,s3,l1,c1,c2,st,dr,mid,l2;
long long sum;
fscanf (fin,"%d",&n);
for (i=1;i<=9;i++)
fscanf (fin,"%lld",&s[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
fscanf (fin,"%lld",&a[i][j]);
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
for (s1=1;s1<=9;s1++){
// stiu s1
for (i=1;i<n;i++){ // caut L1=i
l1=i;
st=1;
dr=n;
while (st<=dr){
mid=(st+dr)/2;
if (a[l1][mid]==s[s1])
break;
else if (a[l1][mid]<s[s1])
st=mid+1;
else dr=mid-1;
}
if (st>dr)
continue; // nu exista niciun C1 posibil pt L1=i si s1
c1=mid;
// am c1 fixat
for (s2=1;s2<=9;s2++){
if (s1==s2)
continue;
// caut binar c2 pt s2 ul curent
st=c1+1;
dr=n;
while (st<=dr){
mid=(st+dr)/2;
if (a[l1][mid]-a[l1][c1]==s[s2])
break;
else if (a[l1][mid]-a[l1][c1]<s[s2])
st=mid+1;
else dr=mid-1;
}
if (st>dr)
continue;
c2=mid;
// mai fixez un s3 si caut binar l2
for (s3=1;s3<=9;s3++){
if (s3==s1 || s3==s2)
continue;
st=i+1;
dr=n;
while (st<=dr){
mid=(st+dr)/2;
if (a[mid][c1]-a[l1][c1]==s[s3])
break;
else if (a[mid][c1]-a[l1][c1]<s[s3])
st=mid+1;
else dr=mid-1;
}
if (st>dr)
continue;
l2=mid; // am practic fixate l1 l2 c1 si c2, verific daca sunt solutii
f.reset();
f[s1]=f[s2]=f[s3]=1;
sum=a[i][n]-a[i][c2];
if (verif(sum)==0)
continue;
sum=a[l2][c2]-a[l2][c1]-a[i][c2]+a[i][c1];
if (verif (sum)==0)
continue;
sum=a[l2][n]-a[i][n]-a[l2][c2]+a[i][c2];
if (verif (sum)==0)
continue;
sum=a[n][c1]-a[l2][c1];
if (verif (sum)==0)
continue;
sum=a[n][n]-a[n][c2]-a[l2][n]+a[l2][c2];
if (verif (sum)==0)
continue;
fprintf (fout,"%d %d %d %d",i,l2,c1,c2);
return 0;
}
}
}
}
return 0;
}