Cod sursa(job #2539035)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 5 februarie 2020 15:53:01
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <iostream>
#include<cstdio>
const int N=515;
long long mat[N][N];
long long spart[N][N];
long long slin[N];
long long scol[N];
long long v[10];
using namespace std;
FILE*fin,*fout;
const int SIZE=1<<10;
char buf[SIZE];
int p=SIZE;
char next_ch(){
  if(p==SIZE){
    fread(buf,sizeof(char),SIZE,fin);
    p=0;
  }
  return buf[p++];
}
long long read(){
  long long x=0;
  char c=next_ch();
  while(!isdigit(c)){
    c=next_ch();
  }
  while(isdigit(c)){
    x=x*10+c-'0';
    c=next_ch();
  }
  return x;
}
long long n;
long long lin1,col1,lin2,col2;
long long cb(long long s[],long long val){
  long long pas=0,p2=1<<9;
  while(p2){
    if(pas+p2<=n && s[pas+p2]<val)
      pas+=p2;
    p2/=2;
  }
  return pas+1;
}
inline long long query(long long l1,long long c1,long long l2,long long 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];
  long long 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(long long k){
  if(k==10){
    solve();
    return;
  }
  for(long long i=k;i<=9;i++){
    swap(v[i],v[k]);
    bkt(k+1);
    swap(v[i],v[k]);
  }
}
int main()
{
  fin=fopen("zone.in","r");
  fout=fopen("zone.out","w");
  n=read();
  for(int i=1;i<=9;i++){
    v[i]=read();
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      mat[i][j]=read();
      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,"%lld %lld %lld %lld",lin1,lin2,col1,col2);
  return 0;
}