Cod sursa(job #3254777)
Utilizator | Data | 8 noiembrie 2024 19:59:09 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 4.59 kb |
#include <fstream>
#include <map>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
map <long long, long long> m1, m2;
int v[513][513], w[10];
int main()
{
int n, l1, l2, c1, c2, st, dr, mid;
fin >> n;
for(int i=1; i<=9; i++)
{
fin >> w[i];
m1[w[i]]++;
m2[w[i]]++;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
fin >> v[i][j];
v[i][j]+=(v[i-1][j]+v[i][j-1]-v[i-1][j-1]);
}
}
for(int i=1; i<=n-2; i++)
{
for(int q=1; q<=9; q++)
{
st=1, dr=n, mid;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[i][mid]==w[q])
break;
else if(v[i][mid]>w[q])
dr = mid-1;
else
st = mid+1;
}
if(st<=dr)
{
l1=i;
c1=mid;
m1[v[l1][c1]]--;
for(int q=1; q<=9; q++)
{
if(m1[w[q]])
{
st=l1+1; dr=n;
while(st<=dr)
{
mid = (st+dr)/2;
if(v[mid][c1]-v[l1][c1]==w[q])
break;
else if(v[mid][c1]-v[l1][c1]>w[q])
dr = mid-1;
else
st = mid+1;
}
if(st<=dr&&m1[v[n][c1]-v[mid][c1]])
{
m1[v[mid][c1]-v[l1][c1]]--;
m1[v[n][c1]-v[mid][c1]]--;
l2=mid;
for(int q=1; q<=9; q++)
{
if(m1[w[q]])
{
st=c1+1; dr=n;
while(st<=dr)
{
mid = (st+dr)/2;
if(v[l1][mid]-v[l1][c1]==w[q])
break;
else if(v[l1][mid]-v[l1][c1]>w[q])
dr = mid-1;
else
st = mid+1;
}
if(st<=dr&&m1[v[l1][n]-v[l1][c2]])
{
c2=mid;
m1[v[l1][mid]-v[l1][c1]]--;
m1[v[l1][n]-v[l1][c2]]--;
bool ok=1;
if(m1[v[l2][c2]-v[l1][c2]-v[l2][c1]+v[l1][c1]])
m1[v[l2][c2]-v[l1][c2]-v[l2][c1]+v[l1][c1]]--;
else
ok=0;
if(m1[v[l2][n]-v[l2][c2]-v[l1][n]+v[l1][c2]])
m1[v[l2][c2]-v[l1][c2]-v[l2][c1]+v[l1][c1]]--;
else
ok=0;
if(m1[v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]])
m1[v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]]--;
else
ok=0;
if(m1[v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]])
m1[v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]]--;
else
ok=0;
if(ok==1)
{
fout << l1 << " " << l2 << " " << c1 << " " << c2;
return 0;
}
}
}
}
}
}
}
}
for(int q=1; q<=9; q++)
{
m1[w[q]] = m2[w[q]];
}
}
}
return 0;
}