Cod sursa(job #2358589)

Utilizator YetoAdrian Tonica Yeto Data 28 februarie 2019 10:32:40
Problema Zone Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.87 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
long long a[515][515];int ok, s1, s2, s3, s4;
int n, m, i, j, l1, c1, l2, c2;long long sum5, sum6, sum7, sum8, sum9;
long long v[10];bool viz[10];

int valid (long long sum5,long long sum6,long long sum7,long long sum8,long long sum9)
{
    for (int s5=1;s5<=9;s5++) {
        if (viz[s5]==0 && sum5==v[s5]) {
            viz[s5]=1;
            for (int s6=1;s6<=9;s6++) {
                if (viz[s6]==0 && sum6==v[s6]) {
                    viz[s6]=1;
                    for (int s7=1;s7<=9;s7++) {
                        if (viz[s7]==0 && sum7==v[s7]) {
                            viz[s7]=1;
                            for (int s8=1;s8<=9;s8++) {
                                if (viz[s8]==0 && sum8==v[s8]) {
                                    viz[s8]=1;
                                    for (int s9=1;s9<=9;s9++) {
                                        if (viz[s9]==0 && sum9==v[s9])
                                            return 1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}

int lcautbin(int st, int dr, int s2)
{

    while (st<=dr) {
        int mid=(st+dr)/2;
        if (a[mid][c1]-a[l1][c1]==s2)
            return mid;
        if (a[mid][c1]-a[l1][c1]<s2)
            st=mid+1;
        else
            dr=mid-1;
    }

    return 0;
}


int cautbin(int st, int dr, int l1, int s1)
{
    int c=st;
    while (st<=dr) {
        int mid = (st+dr)/2;
        if (a[l1][mid]-a[0][mid]-a[l1][c-1]+a[0][c-1]==s1)
            return mid;
        if (a[l1][mid]-a[0][mid]-a[l1][c-1]+a[0][c-1]<s1)
            st=mid+1;
        else
            dr=mid-1;
    }

    return 0;
}

int main () {
    ifstream fin ("zone.in");
    ofstream fout ("zone.out");
    fin>>n;
    for (i=1;i<=9;i++) {
        fin>>v[i];
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++)
            fin>>a[i][j];
    }
    sort(v+1, v+9+1);

    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }

    for (l1=1;l1<=n-2;l1++) {
        memset (viz, 0, sizeof(viz));
        for (s1=1;s1<=9;s1++) {
            if (viz[s1]==0) {
                c1=cautbin(1, n-2, l1, v[s1]);
                if (c1!=0) {
                    viz[s1]=1;
                    for (s2=1;s2<=9;s2++) {
                        if (viz[s2]==0) {
                            c2=cautbin (c1+1, n-1, l1, v[s2]);
                            if (c2!=0) {
                                viz[s2]=1;
                                for (s3=1;s3<=9;s3++) {
                                    if (viz[s3]==0) {
                                        if (a[l1][n]-a[0][n]-a[l1][c2]+a[0][c2]==v[s3]){
                                            viz[s3]=1;
                                            ok=0;
                                            for (s4=1;s4<=9;s4++) {
                                                if (viz[s4]==0) {
                                                    l2=lcautbin(l1+1, n-1, v[s4]);
                                                    if (l2!=0) {
                                                        viz[s4]=1;
                                                        sum5=a[l2][c2]-a[l1][c2]-a[l2][c1]+a[l1][c1];
                                                        sum6=a[l2][n]-a[l1][n]-a[l2][c2]+a[l1][c2];
                                                        sum7=a[n][c1]-a[l2][c1]-a[n][0]+a[l2][0];
                                                        sum8=a[n][c2]-a[l2][c2]-a[n][c1]+a[l2][c1];
                                                        sum9=a[n][n]-a[l2][n]-a[n][c2]+a[l2][c2];
                                                        if (valid(sum5, sum6, sum7, sum8, sum9)) {
                                                            fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
                                                            return 0;
                                                        }
                                                        else
                                                            viz[s4]=0;
                                                    }

                                                }
                                            }
                                        } else
                                            viz[s3]=0;
                                    }
                                }
                            }else
                                viz[s2]=0;
                        }
                    }
                }else
                    viz[s1]=0;
            }
        }
    }
    return 0;
}