Cod sursa(job #2539001)

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

int n;
int lin1,col1,lin2,col2;
int cb(int s[],int val){
  int pas=0,p2=1<<10;
  while(p2){
    if(pas+p2<=n && s[pas+p2]<val)
      pas+=p2;
    p2/=2;
  }
  return pas+1;
}
void solve(){
  int sc1=v[1]+v[2]+v[3],sc2=v[4]+v[5]+v[6];
  int sl1=v[1]+v[4]+v[7],sl2=v[2]+v[5]+v[8];
  if(sc1==51 && sc2==12 && sl1==15 && sl2==45){
    cout<<1;
  }
  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){
    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,"%d",&mat[i][j]);
      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;
}