Cod sursa(job #1759414)
Utilizator | Data | 19 septembrie 2016 09:04:39 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 6.35 kb |
#include<bits/stdc++.h>
#define dim 1000005
#define INF INT_MAX
using namespace std;
int n,seen[15],v[15],a[1005][1005],l1,l2,s[1005][1005],s1,s2,s3,x,c2;
char buff[dim+5];
int poz=0,l1x,l2x,c1x,c2x,c1,st,dr,mid,j2,y;
vector<int> el,el1;
bool find(int x)
{
for(int i=0;i<el.size();i++)
if (el[i]==x) return 1;
return 0;
}
bool cautare(int x)
{
for(int i=1;i<=9;i++)
{
if(v[i]==x && !find(i)) return 1;
}
return 0;
}
void citeste(int &numar)
{
numar=0;
while (buff[poz]<'0' || buff[poz]>'9')
{
poz++;
if (poz==dim)
{
poz=0;
fread(buff,1,dim,stdin);
}
}
while (buff[poz]>='0' && buff[poz]<='9')
{
numar=numar*10+buff[poz]-'0';
poz++;
if (poz==dim)
{
poz=0;
fread(buff,1,dim,stdin);
}
}
}
/*int cautare(int x)
{
int st,dr,mid;
st=1;
dr=9;
while( st<=dr)
{
mid=(st+dr)>>1;
if (val[mid]==x)
{
if (!seen[mid]) return mid;
else
{
int i=mid-1;
while (!(i>=1 && val[i]==x && !seen[i])) i--;
if (val[i]==x) return i;
i=mid+1;
while (!(i<=n && val[i]==x && !seen[i])) i++;
if (val[i]==x) return i;
}
}
else
if (val[mid]<x) st=mid+1;
else dr=mid-1;
}
return 0;
}*/
bool sol=0,ok5,ok7;
int main()
{
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
// scanf("%d",&n);
fread(buff,1,dim,stdin);
citeste(n);
// val.push_back(-1);
for(int i=1;i<=9;i++)
{
//scanf("%d",&val[i]);
citeste(v[i]);
// val.push_back(x);
}
// sort(val+1,val+10);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
//scanf("%d",&a[i][j]);
citeste(a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
s[1][i]=s[1][i-1]+a[1][i];
s[i][1]=s[i-1][1]+a[i][1];
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=9 && !sol;i++)
{
el.clear();
el.push_back(i);
l1x=c1x=l2x=c2x=0;
for(int l1=1;l1<=(n-2);l1++)
{
c1=0;
st=1;
dr=n-2;
while(st<=dr)
{
mid=(st+dr)>>1;
if (s[l1][mid]==v[i])
{
c1=mid;
st=dr+1;
}
else
if (s[l1][mid]<v[i]) st=mid+1;
else dr=mid-1;
}
if (c1)
{
l1x=l1;
c1x=c1;
break;
}
}
if (l1x && c1x)
{
c2x=INF;
for(int j=1;j<=9;j++)
{
if (j!=i)
{
st=c1+1;
dr=n-1;
c2=0;
while(st<=dr)
{
mid=(st+dr)>>1;
if (s[l1x][mid]==(v[i]+v[j]))
{
c2=j;
st=dr+1;
}
else
if (s[l1x][mid]<(v[i]+v[j])) st=mid+1;
else dr=mid-1;
}
if (c2 && c2<c2x) c2x=c2,j2=j;
}
}
if (c2x<INF)
{
el.push_back(j2);
y=s[l1x][n]-s[l1x][c2x];
bool ok=0;
for(int j=1;j<=9;j++)
{
if (v[j]==y && !find(j))
{
ok=1;
}
}
if (!ok) c2x=0;
}
if (c2x)
{
l2x=INF;
for(int j=1;j<=9;j++)
{
if (!find(j))
{
st=l1+1;
dr=n-1;
l2=0;
while (st<=dr)
{
mid=(st+dr)>>1;
if ((s[mid][c1x]-s[l1x][c1x])==v[j])
{
l2=mid;
st=dr+1;
}
else
if ((s[mid][c1x]-s[l1x][c1x])<v[j])
{
st=mid+1;
}
else dr=mid-1;
}
if (l2 && l2<l2x)
{
//l2x=l2;
// j2=j;
el1.clear();
for(int j=0;j<el.size();j++) el1.push_back(el[j]);
el.push_back(j2);
int s5=s[l2][c2x]-s[l2][c1x]-s[l1x][c2x]+s[l1x][c1x];
int s6=s[l2][c2x]-s[l1x][c2x]-s[l2][c1x]+s[l1x][c1x];
int s7=s[n][c1x]-s[l2][c1x];
int s8=s[n][c2x]-s[l2][c2x]-s[n][c1x]+s[l2][c1x];
int s9=s[n][n]-s[n][c2x]-s[l2][n]+s[l2][c2x];
if (cautare(s5) && cautare(s6) && cautare(s7) && cautare(s8) && cautare(s9))
{
l2x=l2;
j2=j;
}
else
{
el.clear();
for(int j=0;j<el1.size();j++)
{
el.push_back(el1[j]);
}
}
}
}
}
if (l2x<INF)
{
{
printf("%d %d %d %d\n",l1x,l2x,c1x,c2x);
sol=1;
}
//
}
}
}
}
}