Cod sursa(job #2481070)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 26 octombrie 2019 13:31:27
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

ifstream f("zone.in");
ofstream g("zone.out");
string buff;

int n, i, j, l1, l2, c1, c2, p, u, m, ok, s1, s2, s3, L1, L2, C1, C2, v[520][520], val;
long long s[10], b[10], a[520][520];
bool viz[10];

char Buff[520*8];

stringstream ss;

int cbc1(){
    p=1;
    u=n-2;
    while(p<=u)
    {
        m=p+((u-p)>>1);
        if(a[l1][m]==s[s1])
            return m;
        if(a[l1][m]<s[s1])
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

int cbl2(){
    p=l1+1;
    u=n-1;
    while(p<=u)
    {
        m=p+((u-p)>>1);
        if(a[m][c1]-a[l1][c1]==s[s2])
            return m;
        if(a[m][c1]-a[l1][c1]<s[s2])
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

int cbc2(){
    p=c1+1;
    u=n-1;
    while(p<=u)
    {
        m=p+((u-p)>>1);
        if(a[l1][m]-a[l1][c1]==s[s3])
            return m;
        if(a[l1][m]-a[l1][c1]<s[s3])
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

void solutie(){
    b[1]=s[s1];
    b[2]=s[s3];
    b[3]=a[l1][n]-a[l1][c2];
    b[4]=s[s2];
    b[5]=a[l2][c2]-a[l2][c1]-b[2];
    b[6]=a[l2][n]-a[l2][c2]-b[3];
    b[7]=a[n][c1]-a[l2][c1];
    b[8]=a[n][c2]-a[l2][c2]-b[7];
    b[9]=a[n][n]-a[l2][n]-b[7]-b[8];
    sort(b+1, b+10);
    bool ok=0;
    for(i=1; i<10; i++)
        if(s[i]!=b[i])
            ok=1;
    if(ok==0)
        if(L1+L2+C1+C2>l1+l2+c1+c2)
        {
            L1=l1;
            L2=l2;
            C1=c1;
            C2=c2;
        }
}

char *pointer;

int main(){
	f>>n;
    for(i=1; i<10; i++)
		f>>s[i];

	for (i=1;i<=n;i++) {
		f.get();
		f.get(Buff,4000);
		pointer = Buff;
		val = 0;
		j = 0;
		while (*pointer) {
			if (*pointer >= '0' && *pointer <= '9') {
				val = val * 10 + *pointer - '0';
			} else {
				v[i][++j] = val;
				val = 0;
			}
			pointer++;
		}
		v[i][++j] = val;

	}
/*
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
			f>>v[i][j];
*/
    sort(s+1, s+10);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            a[i][j]=v[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    L1=5000;
    int N=n-1;
    for(l1=1; l1<N; l1++)
        for(s1=1; s1<10; s1++)
            if( !viz[s1] )
            {
                c1=cbc1();
                viz[s1]=1;
                for(s2=1; s2<10; s2++)
                    if( !viz[s2] )
                    {
                        l2=cbl2();
                        viz[s2]=1;
                        for(s3=1; s3<10; s3++)
                        {
                            if( !viz[s3] )
                            {
                                c2=cbc2();
                                solutie();
                            }
                        }
                        viz[s2]=0;
                    }
                viz[s1]=0;
            }
	g<<L1<<' '<<L2<<' '<<C1<<' '<<C2<<"\n";
    return 0;
}