Cod sursa(job #2072065)
Utilizator | Data | 21 noiembrie 2017 12:54:16 | |
---|---|---|---|
Problema | Zone | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.62 kb |
#include <fstream>
using namespace std;
ifstream fin ("zone.in");
ofstream fout("zone.out");
long long v[514][514],s[11];
long long f[11], i, j, n,c1,c2,l1,l2,k1,k2,k3,st,dr,mid;
int verificare()
{
int i;
int ok=1;
for(i=1;i<=9;i++)
if(0LL+v[l1][n]-v[l1][c2]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[n][c1]-v[l2][c1]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[l2][c2]-v[l2][c1]-v[l1][c2]+v[l1][c1]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[l2][n]-v[l2][c2]-v[l1][n]+v[l1][c2]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
if(0LL+v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]==s[i]&&f[i]==0)
f[i]=1;
for(i=1;i<=9;i++)
{
if(f[i]==0)
ok=0;
f[i]=0;
}
return ok;
}
int main ()
{
fin>>n;
for(i=1;i<=9;i++)
fin>>s[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
fin>>v[i][j];
v[i][j]+=v[i][j-1]+v[i-1][j]-v[i-1][j-1];
}
for(k1=1;k1<=9;k1++)
for(k2=1;k2<=9;k2++)
if(k2!=k1)
for(k3=1;k3<=9;k3++)
if(k3!=k2&&k3!=k1)
for(l1=1;l1<n-1;l1++)
{
l2=-1;c1=-1;c2=-1;
st=1;
dr=n-2;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[l1][mid]<=s[k1])
{
if(v[l1][mid]==s[k1])
{
if(c1==-1)
c1=mid;
else
c1=min(c1, mid);
}
st=mid+1;
}
else
dr=mid-1;
}
if(v[l1][c1]!=s[k1])
continue;
st=l1+1;
dr=n-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[mid][c1]-v[l1][c1]<=s[k3])
{
if(v[mid][c1]-v[l1][c1]==s[k3])
{
if(l2==-1)
l2=mid;
else
l2=min(l2, mid);
}
st=mid+1;
}
else
dr=mid-1;
}
if(v[l2][c1]-v[l1][c1]!=s[k3])
continue;
st=c1+1;
dr=n-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[l1][mid]-v[l1][c1]<=s[k2])
{
if(v[l1][mid]-v[l1][c1]==s[k2])
{
if(c2==-1)
c2=mid;
else
c2=min(c2, mid);
}
st=mid+1;
}
else
dr=mid-1;
}
if(v[l1][c2]-v[l1][c1]!=s[k2])
continue;
f[k1]=1;
f[k2]=1;
f[k3]=1;
if(verificare()==1)
{
fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";
return 0;
}
}
return 0;
}