Cod sursa(job #2330019)

Utilizator shantih1Alex S Hill shantih1 Data 27 ianuarie 2019 19:17:06
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#define ll long long

using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");

int n,i,j,i1,i2,i3,l1,l2,c1,c2,l,r,m,x;
ll v[10],z[10],h[10],b[10],s[520][520],k;
struct per
{	int l1,l2,c1,c2;
	bool operator<(const per &alt)const
	{	
		if(l1!=alt.l1)	return l1<alt.l1;
		if(c1!=alt.c1)	return c1<alt.c1;
		if(l2!=alt.l2)	return l2<alt.l2;
		return c2<alt.c2;
	}
} rz,aux;
inline ll sum(int x,int y,int x2,int y2)
{	return s[x][y]-s[x2-1][y]-s[x][y2-1]+s[x2-1][y2-1];	}

void check(int l1,int l2,int c1,int c2)
{
	b[1]=sum(l1,c1,1,1);
	b[2]=sum(l1,c2,1,c1+1);
	b[3]=sum(l1,n,1,c2+1);
	b[4]=sum(l2,c1,l1+1,1);
	b[5]=sum(l2,c2,l1+1,c1+1);
	b[6]=sum(l2,n,l1+1,c2+1);
	b[7]=sum(n,c1,l2+1,1);
	b[8]=sum(n,c2,l2+1,c1+1);
	b[9]=sum(n,n,l2+1,c2+1);
	sort(b+1,b+10);
	
	for(int i=1;i<=9;i++)
		if(b[i]!=h[i])	return;
		
	aux={l1,l2,c1,c2};
	if(rz.l1==0 || aux<rz)
		rz=aux;
}

int main() {
	
	fin>>n;
	for(i=1;i<=9;i++)
		fin>>v[i], h[i]=v[i];
	
	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];
	sort(h+1,h+10);
	
	for(l1=1;l1<=n-2;l1++)
		for(i1=1;i1<=9;i1++)
		{
			z[i1]=1;
			c1=0;
			l=1;	r=n-2;
			while(l<=r)
			{
				m=(l+r)/2;
				k=sum(l1,m,1,1);
				if(k>v[i1])		r=m-1;
				else			l=m+1;
				if(k==v[i1])	c1=m, l=r+1;
			}
			if(!c1)	z[i1]=0;
			if(c1)
				for(i2=1;i2<=9;i2++)
					if(z[i2]==0)
					{
						z[i2]=1;
						c2=0;
						l=c1+1;	r=n-1;
						while(l<=r)
						{
							m=(l+r)/2;
							k=sum(l1,m,1,c1+1);
							if(k>v[i2])		r=m-1;
							else			l=m+1;
							if(k==v[i2])	c2=m, l=r+1;
						}
						if(!c2)	z[i2]=0;
						if(c2)
						{
							x=0;
							k=sum(l1,n,1,c2+1);
							for(j=1;j<=9;j++)
								if(z[j]==0 && v[j]==k)	x=j, z[j]=1;
							
							if(x)
								for(i3=1;i3<=9;i3++)
									if(z[i3]==0)
									{
										l2=0;
										l=l1+1;	r=n-1;
										while(l<=r)
										{
											m=(l+r)/2;
											k=sum(m,c1,l1+1,1);
											if(k>v[i3])		r=m-1;
											else			l=m+1;
											if(k==v[i3])	l2=m, l=r+1;
										}
										if(l2)
											check(l1,l2,c1,c2);
									}
							z[x]=0;
						}
					}
		}
	fout<<rz.l1<<" "<<rz.l2<<" "<<rz.c1<<" "<<rz.c2<<"\n";
}