Cod sursa(job #3238667)
Utilizator | Data | 28 iulie 2024 17:45:59 | |
---|---|---|---|
Problema | Zone | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 4.71 kb |
#include <fstream>
#include <unordered_map>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
long long s[515][515],i,j,ln1,ln2,c1,c2,n,v[15],st,dr,mij;
unordered_map <long long,long long> m;
long long suma(long long x1,long long y1,long long x2,long long y2)
{
return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n;
for (i=1; i<=9; i++)
{fin>>v[i]; m[v[i]]++;}
sort(v+1,v+10);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
{
fin>>s[i][j];
s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
for (ln1=1; ln1<=n-2; ln1++)
for (c1=1; c1<=n-2; c1++)
if (m[s[ln1][c1]]!=0)
{
m[s[ln1][c1]]--;
for (i=1; i<=9; i++)
if (m[v[i]])
{
st=ln1+1; dr=n-1;
while (st<=dr)
{
mij=(st+dr)>>1;
if (s[mij][c1]-s[ln1][c1]<v[i])
st=mij+1;
else
if (s[mij][c1]-s[ln1][c1]>v[i])
dr=mij-1;
else
break;
}
if (s[mij][c1]-s[ln1][c1]==v[i])
{
ln2=mij; m[v[i]]--;
if (m[s[n][c1]-s[ln2][c1]])
{
m[s[n][c1]-s[ln2][c1]]--;
for (j=1; j<=9; j++)
if (m[v[j]])
{
st=c1+1; dr=n-1;
while (st<=dr)
{
mij=(st+dr)>>1;
if (s[ln1][mij]-s[ln1][c1]<v[j])
st=mij+1;
else
if (s[ln1][mij]-s[ln1][c1]>v[j])
dr=mij-1;
else
break;
}
if (s[ln1][mij]-s[ln1][c1]==v[j])
{
c2=mij; m[v[j]]--;
if (m[suma(ln1+1,c1+1,ln2,c2)])
{
m[suma(ln1+1,c1+1,ln2,c2)]--;
if (m[suma(ln2+1,c1+1,n,c2)])
{
m[suma(ln2+1,c1+1,n,c2)]--;
if (m[s[ln1][n]-s[ln1][c2]])
{
m[s[ln1][n]-s[ln1][c2]]--;
if (m[suma(ln1+1,c2+1,ln2,n)])
{
m[suma(ln1+1,c2+1,ln2,n)]--;
if (suma(ln2+1,c2+1,n,n))
{
fout<<ln1<<" "<<ln2<<" "<<c1<<" "<<c2;
return 0;
}
m[suma(ln1+1,c2+1,ln2,n)]++;
}
m[s[ln1][n]-s[ln1][c2]]++;
}
m[suma(ln2+1,c1+1,n,c2)]++;
}
m[suma(ln1+1,c1+1,ln2,c2)]++;
}
m[v[j]]++;
}
}
m[s[n][c1]-s[ln2][c1]]++;
}
m[v[i]]++;
}
}
m[s[ln1][c1]]++;
}
return 0;
}