Cod sursa(job #2357944)
Utilizator | Data | 27 februarie 2019 20:20:46 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 5.49 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
int a[515][515];
int s[10];
bool viz[10];
int x,n;
int cautbin_lin(int l1, int c1, int l2, int c2, int val)
{
int st=l1,dr=l2;
while(st<=dr)
{
int mid=(st+dr)/2;
int x=a[mid][c2]+a[l1-1][c1-1]-a[mid][c1-1]-a[l1-1][c2];
if(x==val)
return mid;
else if(x>val)
dr=mid-1;
else if(x<val)
st=mid+1;
}
return -1;
}
int cautbin_col(int l1, int c1, int l2, int c2, int val)
{
int st=c1,dr=c2;
while(st<=dr)
{
int mid=(st+dr)/2;
int x=a[l2][mid]+a[l1-1][c1-1]-a[l2][c1-1]-a[l1-1][mid];
if(x==val)
return mid;
else if(x>val)
dr=mid-1;
else if(x<val)
st=mid+1;
}
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(1,1,l1,n-2,s[s1]);
viz[s1]=1;
for(int s2=1;s2<=9;s2++)
if(!viz[s2])
{
int c2=cautbin_col(1,c1+1,l1,n-1,s[s2]);
if(c2!=-1)
{
viz[s2]=1;
int sum3=a[l1][n]+a[0][c2-1]-a[l1][c2-1]-a[0][n];
for(int s3=1;s3<=9;s3++)
{
if(!viz[s3]&&s[s3]==sum3)
{
viz[s3]=1;
for(int s4=1;s4<=9;s4++)
if(!viz[s4])
{
int l2=cautbin_lin(l1+1,1,n-1,c1,s[s4]);
if(l2!=-1)
{
viz[s4]=1;
int sum5=a[l2][c2]+a[l1-1][c1-1]-a[l2][c1-1]-a[l1-1][c2];
for(int s5=1;s5<=9;s5++)
{
if(!viz[s5]&&s[s5]==sum5)
{
viz[s5]=1;
int sum6=a[l2][n]+a[l1-1][c2-1]-a[l2][c2-1]-a[l2-1][n];
for(int s6=1;s6<=9;s6++)
{
if(!viz[s6]&&s[s6]==sum6)
{
viz[s6]=1;
int sum7=a[n][c1]+a[l2-1][0]-a[n][0]-a[l2-1][c1];
for(int s7=1;s7<=9;s7++)
{
if(!viz[s7]&&s[s7]==sum7)
{
viz[s7]=1;
int sum8=a[n][c2]+a[l2-1][c2-1]-a[n][c1-1]-a[l2-1][c2];
for(int s8=1;s8<=9;s8++)
{
if(!viz[s8]&&s[s8]==sum8)
{
fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
return 0;
}
}
viz[s7]=0;
}
}
viz[s6]=0;
}
}
viz[s5]=0;
}
}
viz[s4]=0;
}
}
viz[s3]=0;
}
}
}
viz[s2]=0;
}
viz[s1]=0;
}
return 0;
}