Cod sursa(job #2197320)
Utilizator | Data | 21 aprilie 2018 18:30:10 | |
---|---|---|---|
Problema | Zone | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.18 kb |
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
const int N=512;
int n,v[N+5][N+5];
long long sir[100];
long long s[N+5][N+5];
int r1,c1,r2,c2;
bool viz[100];
long long sum(int r1,int c1,int r2,int c2)
{
return s[r2][c2]-s[r2][c1-1]-s[r1-1][c2]+s[r1-1][c1-1];
}
int main()
{
fin>>n;
for(int i=1;i<=9;i++)
fin>>sir[i];
sort(sir+1,sir+9+1);
for(int i=1;i<=n;i++)
{
long long cur=0;
for(int j=1;j<=n;j++)
{
fin>>v[i][j];
cur+=v[i][j];
s[i][j]=s[i-1][j]+cur;
}
}
for(r1=1;r1<=n;r1++)
{
for(int v1=1;v1<=9;v1++)
{
int r=0,pas=(1<<9);
while(pas)
{
if(r+pas<=n && sum(1,1,r1,r+pas)<=sir[v1])
r+=pas;
pas/=2;
}
if(sum(1,1,r1,r+pas)==sir[v1])
{
viz[v1]=1;
c1=r;
for(int v2=1;v2<=9;v2++)
if(viz[v2]==0)
{
r=c1+1;
pas=(1<<9);
while(pas)
{
if(r+pas<=n && sum(1,c1+1,r1,r+pas)<=sir[v2])
r+=pas;
pas/=2;
}
if(sum(1,c1+1,r1,r)==sir[v2])
{
viz[v2]=1;
c2=r;
for(int v3=1;v3<=9;v3++)
if(viz[v3]==0)
{
r=r1+1;
pas=(1<<9);
while(pas)
{
if(r+pas<=n && sum(r1+1,1,r+pas,c1)<=sir[v3])
r+=pas;
pas/=2;
}
if(sum(r1+1,1,r,c1)==sir[v3])
{
r2=r;
viz[v3]=1;
long long val3,val5,val6,val7,val8,val9;
val3=sum(1,c2+1,r1,n);
val5=sum(r1+1,c1+1,r2,c2);
val6=sum(r1+1,c2+1,r2,n);
val7=sum(r2+1,1,n,c1);
val8=sum(r2+1,c1+1,n,c2);
val9=sum(r2+1,c2+1,n,n);
int g3=0,g5=0,g6=0,g7=0,g8=0,g9=0;
for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val3){viz[i]=1;g3=1;}
for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val5){viz[i]=1;g5=1;}
for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val6){viz[i]=1;g6=1;}
for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val7){viz[i]=1;g7=1;}
for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val8){viz[i]=1;g8=1;}
for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val9){viz[i]=1;g9=1;}
if(g3*g5*g6*g7*g8*g9==1)
{
fout<<r1<<" "<<r2<<" "<<c1<<" "<<c2;
return 0;
}
memset(viz,0,sizeof(viz));
viz[v1]=viz[v2]=1;
}
}
viz[v2]=0;
}
}
viz[v1]=0;
}
}
}
return 0;
}
/**
**/