Cod sursa(job #2539019)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 5 februarie 2020 15:32:35
Problema Zone Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include<cstdio>
const int N=515;
long long mat[N][N];
int spart[N][N];
long long slin[N];
long long scol[N];
long long v[10];
using namespace std;

int n;
int lin1,col1,lin2,col2;
int cb(long long s[],long long val){
  int pas=0,p2=1<<10;
  while(p2){
    if(pas+p2<=n && s[pas+p2]<val)
      pas+=p2;
    p2/=2;
  }
  return pas+1;
}
inline long long query(int l1,int c1,int l2,int c2){
  return spart[l2][c2]-spart[l2][c1]-spart[l1][c2]+spart[l1][c1];
}
void solve(){
  long long sc1=v[1]+v[2]+v[3],sc2=v[4]+v[5]+v[6];
  long long sl1=v[1]+v[4]+v[7],sl2=v[2]+v[5]+v[8];
  int l1=cb(slin,sl1),l2=cb(slin,sl1+sl2),c1=cb(scol,sc1),c2=cb(scol,sc1+sc2);
  if(slin[l1]==sl1 && slin[l2]==sl1+sl2 && scol[c1]==sc1 && scol[c2]==sc1+sc2 && query(0,0,l1,c1)==v[1] && query(l1,0,l2,c1)==v[2] && query(l2,0,n,c1)==v[3] && query(0,c1,l1,c2)==v[4] && query(l1,c1,l2,c2)==v[5] && query(l2,c1,n,c2)==v[6] && query(0,c2,l1,n)==v[7] && query(l1,c2,l2,n)==v[8] && query(l2,c2,n,n)==v[9]){
    if(lin1==0)
      lin1=l1,lin2=l2,col1=c1,col2=c2;
    else if(l1<lin1)
      lin1=l1,lin2=l2,col1=c1,col2=c2;
    else if(l1==lin1 && c1<col1)
      lin1=l1,lin2=l2,col1=c1,col2=c2;
    else if(l1==lin1 && c1==col1 && l2<lin2)
      lin1=l1,lin2=l2,col1=c1,col2=c2;
    else if(l1==lin1 && c1==col1 && l2==lin2 && c2<col2)
      lin1=l1,lin2=l2,col1=c1,col2=c2;
  }
}

void bkt(int k){
  if(k==10){
    solve();
    return;
  }
  for(int i=k;i<=9;i++){
    swap(v[i],v[k]);
    bkt(k+1);
    swap(v[i],v[k]);
  }
}
int main()
{
  FILE*fin,*fout;
  fin=fopen("zone.in","r");
  fout=fopen("zone.out","w");
  fscanf(fin,"%d",&n);
  for(int i=1;i<=9;i++){
    fscanf(fin,"%d",&v[i]);
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      fscanf(fin,"%lld",&mat[i][j]);
      spart[i][j]=mat[i][j]+spart[i-1][j]+spart[i][j-1]-spart[i-1][j-1];
      slin[i]+=mat[i][j];
      scol[j]+=mat[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    slin[i]+=slin[i-1];
    scol[i]+=scol[i-1];
  }
  bkt(1);
  fprintf(fout,"%d %d %d %d",lin1,lin2,col1,col2);
  return 0;
}