Cod sursa(job #3335685)

Utilizator vldftzFlorea Vlad hackuit vldftz Data 23 ianuarie 2026 10:56:56
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.04 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Triple {
    ll a,b,c;
    bool operator==(Triple const& o) const {
        return a==o.a && b==o.b && c==o.c;
    }
};
struct TripleHash {
    size_t operator()(Triple const& t) const noexcept {
        uint64_t x = (uint64_t)t.a * 1000003ULL + (uint64_t)t.b;
        x = x * 1000003ULL + (uint64_t)t.c;
        return (size_t)(x ^ (x>>32));
    }
};

int main(){
    FILE *fin  = fopen("zone.in", "r");
    FILE *fout = fopen("zone.out", "w");

    int N;
    fscanf(fin, "%d", &N);

    vector<ll> S(9);
    for(int i=0;i<9;i++) fscanf(fin, "%lld", &S[i]);

    vector<vector<ll>> a(N, vector<ll>(N));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            fscanf(fin, "%lld", &a[i][j]);

    // prefix pe coloane
    vector<vector<ll>> col_pref(N, vector<ll>(N,0));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            col_pref[i][j] = a[i][j] + (i?col_pref[i-1][j]:0);

    vector<ll> col_total(N);
    for(int j=0;j<N;j++) col_total[j] = col_pref[N-1][j];

    vector<ll> row_sum(N,0), row_pref(N,0);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) row_sum[i]+=a[i][j];
        row_pref[i] = row_sum[i] + (i?row_pref[i-1]:0);
    }

    struct Part {
        array<int,3> g1,g2,g3;
        ll s1,s2,s3;
    };
    map<array<ll,3>, vector<Part>> parts;

    vector<int> idx(9);
    iota(idx.begin(), idx.end(), 0);

    for(int a1=0;a1<9;a1++)
        for(int a2=a1+1;a2<9;a2++)
            for(int a3=a2+1;a3<9;a3++){
                vector<int> rem;
                for(int i=0;i<9;i++)
                    if(i!=a1 && i!=a2 && i!=a3) rem.push_back(i);

                for(int b1=0;b1<6;b1++)
                    for(int b2=b1+1;b2<6;b2++)
                        for(int b3=b2+1;b3<6;b3++){
                            array<int,3> g1={a1,a2,a3};
                            array<int,3> g2={rem[b1],rem[b2],rem[b3]};
                            vector<int> used(9,0);
                            for(int x:g1) used[x]=1;
                            for(int x:g2) used[x]=1;
                            array<int,3> g3;
                            int p=0;
                            for(int i=0;i<9;i++) if(!used[i]) g3[p++]=i;

                            vector<array<int,3>> gs={g1,g2,g3};
                            sort(gs.begin(),gs.end(),[](auto &x, auto &y){
                                return vector<int>(x.begin(),x.end()) <
                                       vector<int>(y.begin(),y.end());
                            });

                            ll s1=S[gs[0][0]]+S[gs[0][1]]+S[gs[0][2]];
                            ll s2=S[gs[1][0]]+S[gs[1][1]]+S[gs[1][2]];
                            ll s3=S[gs[2][0]]+S[gs[2][1]]+S[gs[2][2]];
                            array<ll,3> key={s1,s2,s3};
                            sort(key.begin(),key.end());
                            parts[key].push_back({gs[0],gs[1],gs[2],s1,s2,s3});
                        }
            }

    for(int l1=1;l1<=N-2;l1++){
        bool ok=false;
        int best_l2=0,best_c1=0,best_c2=0;
        ll best_sum=LLONG_MAX;

        for(int l2=l1+1;l2<=N-1;l2++){
            ll top=row_pref[l1-1];
            ll mid=row_pref[l2-1]-row_pref[l1-1];
            ll bot=row_pref[N-1]-row_pref[l2-1];

            array<ll,3> key={top,mid,bot};
            sort(key.begin(),key.end());
            if(!parts.count(key)) continue;

            vector<ll> Ptop(N+1,0),Pmid(N+1,0),Pbot(N+1,0);
            for(int j=0;j<N;j++){
                ll t=col_pref[l1-1][j];
                ll m=col_pref[l2-1][j]-col_pref[l1-1][j];
                ll b=col_total[j]-col_pref[l2-1][j];
                Ptop[j+1]=Ptop[j]+t;
                Pmid[j+1]=Pmid[j]+m;
                Pbot[j+1]=Pbot[j]+b;
            }

            unordered_map<Triple, vector<int>, TripleHash> mp;
            for(int c=1;c<=N-1;c++)
                mp[{Ptop[c],Pmid[c],Pbot[c]}].push_back(c);

            for(auto &P:parts[key]){
                array<array<int,3>,3> G={P.g1,P.g2,P.g3};
                array<ll,3> sum={P.s1,P.s2,P.s3};
                array<int,3> p={0,1,2};
                do{
                    if(sum[p[0]]!=top || sum[p[1]]!=mid || sum[p[2]]!=bot) continue;

                    ll T[3][3];
                    for(int i=0;i<3;i++)
                        for(int j=0;j<3;j++)
                            T[i][j]=S[G[p[i]][j]];

                    for(int c1=1;c1<=N-2;c1++){
                        Triple A={Ptop[c1],Pmid[c1],Pbot[c1]};
                        for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++){
                            if(T[0][i]!=A.a||T[1][j]!=A.b||T[2][k]!=A.c) continue;
                            for(int bi=0;bi<2;bi++) for(int bj=0;bj<2;bj++) for(int bk=0;bk<2;bk++){
                                ll B0=T[0][bi+(bi>=i)];
                                ll B1=T[1][bj+(bj>=j)];
                                ll B2=T[2][bk+(bk>=k)];
                                Triple need={A.a+B0,A.b+B1,A.c+B2};
                                if(!mp.count(need)) continue;
                                for(int c2:mp[need]) if(c2>c1){
                                    ll s=l1+l2+c1+c2;
                                    if(!ok || make_tuple(c1,l2,s)<make_tuple(best_c1,best_l2,best_sum)){
                                        ok=true;
                                        best_c1=c1; best_l2=l2; best_c2=c2;
                                        best_sum=s;
                                    }
                                    break;
                                }
                            }
                        }
                    }
                }while(next_permutation(p.begin(),p.end()));
            }
        }

        if(ok){
            fprintf(fout,"%d %d %d %d\n",l1,best_l2,best_c1,best_c2);
            fclose(fin);
            fclose(fout);
            return 0;
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}