Cod sursa(job #2536116)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 1 februarie 2020 15:20:33
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("zone.in");
ofstream out("zone.out");
long long v[10],sum[257][257],va[6],vb[6];
bool ver[10];
int main() {
    int n,i,r,pas,j,k;
    long long x;
    in>>n;
    for(i=1; i<=9; i++)
        in>>v[i];
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++) {
            in>>x;
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
        }
    for(i=1; i<=n; i++) {
        for(j=1; j<=n; j++) {
            ///for(k=1; k<=9; k++)
            ///ver[k]=0;
            for(k=1; k<=9; k++)
                if(sum[i][j]==v[k])
                    break;
            if(k!=10) {
                ver[k]=1; /// 1
                for(k=1; k<=9; k++)
                    if(!ver[k]) {
                        r=j;
                        pas=1<<8;
                        while(pas) {
                            if(r+pas<=n&&sum[i][r+pas]-sum[i][j]<=v[k])
                                r+=pas;
                            pas/=2;
                        }
                        if(sum[i][r]-sum[i][j]==v[k]) {
                            int k1=k;
                            ver[k]=1;/// 2
                            for(k=1; k<=9; k++)
                                if(!ver[k]&&sum[i][n]-sum[i][r]==v[k])
                                    break;
                            if(k!=10) {
                                ver[k]=1;/// 3
                                int k2=k;
                                for(k=1; k<=9; k++)
                                    if(!ver[k]) {
                                        int r1=i;
                                        pas=1<<8;
                                        while(pas) {
                                            if(r1+pas<=n&&sum[r1+pas][j]-sum[i][j]<=v[k])
                                                r1+=pas;
                                            pas/=2;
                                        }
                                        if(sum[r1][j]-sum[i][j]==v[k]) {
                                            ver[k]=1; /// 4
                                            int cnt=0,k3=k;
                                            for(k=1; k<=9; k++)
                                                if(!ver[k])
                                                    va[++cnt]=v[k];
                                            sort(va+1,va+cnt+1);
                                            ver[k3]=0;
                                            vb[1]=sum[n][j]-sum[r1][j]; /// 7
                                            vb[2]=sum[r1][r]-sum[r1][j]-sum[i][r]+sum[i][j]; ///5
                                            vb[3]=sum[r1][n]-sum[r1][r]-sum[i][n]+sum[i][r]; ///6
                                            vb[4]=sum[n][r]-sum[r1][r]-sum[n][j]+sum[r1][j]; ///8
                                            vb[5]=sum[n][n]-sum[n][r]-sum[r1][n]+sum[r1][r]; ///9
                                            sort(vb+1,vb+6);
                                            int s,t;
                                            for(s=1,t=1; s<=6; s++)
                                                if(va[s]==vb[t])
                                                    t++;
                                            if(t==6) {
                                                out<<i<<" "<<r1<<" "<<j<<" "<<r;
                                                return 0;
                                            }
                                        }
                                    }
                                ver[k2]=0;
                            }
                            ver[k1]=0;
                        }
                    }
            }
        }
    }
    return 0;
}