Cod sursa(job #2544416)

Utilizator mirceagavrizimircea luca gavrizi mirceagavrizi Data 11 februarie 2020 23:57:30
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.56 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int v[10];
int a[515][515],v2[11],v3[11];
int main(){
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    int n,i,j,st,dr,mij,ok,ok2,p1,p2,nr,h,s=0;
    scanf("%d",&n);
    for(i=1;i<=9;i++)
        scanf("%d",&v[i]);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    for(h=1;h<=9;h++){
        for(i=1;i<=n-2;i++){
            for(j=1;j<=n-2;j++){
                if(a[i][j]==v[h]){
                    for(int g=1;g<=9;g++){
                        for(int f=1;f<=9;f++){
                            if(g!=f&&g!=h&&f!=h){
                                st=j+1;
                                dr=n-1;
                                ok=0;
                                while(st<=dr&&ok!=1){
                                    mij=(st+dr)/2;
                                    nr=a[i][mij]-a[i][j];
                                    if(nr==v[g]){
                                        ok=1;
                                        p1=mij;
                                    }
                                    else if(nr<v[g])
                                        st=mij+1;
                                    else
                                        dr=mij-1;
                                }
                                st=i+1;
                                dr=n-1;
                                ok2=0;
                                while(st<=dr&&ok2!=1){
                                    mij=(st+dr)/2;
                                    nr=a[mij][j]-a[i][j];
                                    if(nr==v[f]){
                                        ok2=1;
                                        p2=mij;
                                    }
                                    else if(nr<v[f])
                                        st=mij+1;
                                    else
                                        dr=mij-1;
                                }
                                if(ok==1&&ok2==1){
                                    v2[1]=a[i][n]-a[i][p1];
                                    v2[2]=a[n][j]-a[p2][j];
                                    v2[3]=a[p2][p1]-a[p2][j]-a[i][p1]+a[i][j];
                                    v2[4]=a[p2][n]-a[p2][p1]-a[i][n]+a[i][p1];
                                    v2[5]=a[n][p1]-a[n][j]-a[p2][p1]+a[p2][j];
                                    v2[6]=a[n][n]-a[p2][n]-a[n][p1]+a[p2][p1];
                                    v2[7]=v[h];
                                    v2[8]=v[f];
                                    v2[9]=v[g];
                                    for(int w=1;w<=9;w++)
                                        v3[w]=v[w];
                                    sort(v2+1,v2+10);
                                    sort(v3+1,v3+10);
                                    int okk=0;
                                    for(int w=1;w<=9;w++)
                                        if(v2[w]!=v3[w])
                                            okk=1;
                                    if(okk==0&&s!=1){
                                        printf("%d %d %d %d\n",i,p2,j,p1);
                                        s=1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}