Cod sursa(job #3254816)
Utilizator | Data | 8 noiembrie 2024 21:22:57 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 4.72 kb |
#include <fstream>
#include <unordered_map>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
unordered_map <int, int> m1, m2;
int v[1000][1000], w[100];
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]);
}
}
sort(w+1, w+10);
for(int i=1; i<=n-2; i++)
{
for(int q=1; q<=9; q++)
{
st=0, dr=n+1, mid;
while(st<dr-1)
{
mid=(st+dr)/2;
if(v[i][mid]<w[q])
st = mid;
else
dr = mid;
}
if(v[i][dr]==w[q])
{
l1=i;
c1=dr;
m1[v[l1][c1]]--;
for(int q=1; q<=9; q++)
{
if(m1[w[q]])
{
st=l1; dr=n+1;
while(st<dr-1)
{
mid = (st+dr)/2;
if(v[mid][c1]-v[l1][c1]<w[q])
st = mid;
else
dr = mid;
}
if(v[dr][c1]-v[l1][c1]==w[q]&&m1[v[n][c1]-v[dr][c1]])
{
m1[v[dr][c1]-v[l1][c1]]--;
m1[v[n][c1]-v[dr][c1]]--;
l2=dr;
for(int q=1; q<=9; q++)
{
if(m1[w[q]])
{
st=c1; dr=n+1;
while(st<dr-1)
{
mid = (st+dr)/2;
if(v[l1][mid]-v[l1][c1]<w[q])
st = mid;
else
dr = mid;
}
if(v[l1][dr]-v[l1][c1]==w[q]&&m1[v[l1][n]-v[l1][c2]])
{
c2=dr;
m1[v[l1][dr]-v[l1][c1]]--;
m1[v[l1][n]-v[l1][c2]]--;
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]]--;
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]]--;
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]]--;
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]]--;
fout << l1 << " " << l2 << " " << c1 << " " << c2;
return 0;
}
m1[v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]]++;
}
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]]++;
}
m1[v[l1][dr]-v[l1][c1]]++;
m1[v[l1][n]-v[l1][c2]]++;
}
}
}
m1[v[dr][c1]-v[l1][c1]]++;
m1[v[n][c1]-v[dr][c1]]++;
}
}
}
m1[v[l1][c1]]++;
}
}
}
return 0;
}