Cod sursa(job #3196384)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 23 ianuarie 2024 19:40:21
Problema Zone Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=1024;

int N;
int mat[NMAX][NMAX];
long long int s[NMAX][NMAX];
long long int v[9];

long long int sum(int i0, int j0, int i1, int j1)
{
	return s[i1+1][j1+1]-s[i0][j1+1]-s[i1+1][j0]+s[i0][j0];
}

void build()
{
	int i, j;

	for(i=0;i<N;++i)
		for(j=0;j<N;++j)
			s[i+1][j+1]=mat[i][j]+s[i][j+1]+s[i+1][j]-s[i][j];
}

bool tryVals(int i0, int i1, int j0, int j1)
{
	int u[9], i;
	u[0]=sum(0, 0, i0, j0);
	u[1]=sum(0, j0+1, i0, j1);
	u[2]=sum(0, j1+1, i0, N-1);
	u[3]=sum(i0+1, 0, i1, j0);
	u[4]=sum(i0+1, j0+1, i1, j1);
	u[5]=sum(i0+1, j1+1, i1, N-1);
	u[6]=sum(i1+1, 0, N-1, j0);
	u[7]=sum(i1+1, j0+1, N-1, j1);
	u[8]=sum(i1+1, j1+1, N-1, N-1);

	std::sort(u, u+9);
	for(i=0;i<9;++i)
		if(u[i]!=v[i])
			return 0;
	return 1;
}

int main()
{
	FILE* f=fopen("zone.in", "r"), *g=fopen("zone.out", "w");
//	FILE* f=stdin, *g=stdout;
	int i, j, k, l, m, n;
	int L[2]={NMAX, NMAX}, C[2]={NMAX, NMAX};
	long long int s;

	fscanf(f, "%d", &N);
	for(i=0;i<9;++i)
		fscanf(f, "%lld", v+i);
	std::sort(v, v+9);
	for(i=0;i<N;++i)
		for(j=0;j<N;++j)
			fscanf(f, "%d", mat[i]+j);

	build();

	for(k=0;k<9;++k)
	{
		i=0;
		j=N-3;

		while(i+2<N && j>-1)
		{
			s=sum(0, 0, i, j);
			if(s<v[k])
			{
				++i;
			}
			else if(s>v[k])
			{
				--j;
			}
			else
			{
				for(l=0;l<9;++l)
				{
					if(l!=k)
					{
						m=i+2;
						n=N-1;
						while(m<N && n>j+1)
						{
							s=sum(m, n, N-1, N-1);
							if(s>v[l])
							{
								++m;
							}
							else if(s<v[l])
							{
								--n;
							}
							else
							{
								if(tryVals(i, m-1, j, n-1))
								{
									if(i+1<L[0])
									{
										L[0]=i+1;
										L[1]=m;
										C[0]=j+1;
										C[1]=n;
									}
									else if(i+1==L[0] && j+1<C[0])
									{
										L[0]=i+1;
										L[1]=m;
										C[0]=j+1;
										C[1]=n;
									}
									else if(i+1==L[0] && m<L[1] && j+1==C[0])
									{
										L[0]=i+1;
										L[1]=m;
										C[0]=j+1;
										C[1]=n;
									}
									else if(i+1==L[0] && m==L[1] && j+1==C[0] && n<C[1])
									{
										L[0]=i+1;
										L[1]=m;
										C[0]=j+1;
										C[1]=n;
									}
									fprintf(g, "%d %d %d %d\n", i+1, m, j+1, n);
								}
								--n;
								++m;
							}
						}
					}
				}
				--j;
				++i;
			}
		}
	}

	fclose(f);
	fclose(g);
	return 0;
}