Cod sursa(job #2544416)
Utilizator | Data | 11 februarie 2020 23:57:30 | |
---|---|---|---|
Problema | Zone | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 3.56 kb |
#include<stdio.h>
#include<algorithm>
using namespace std;
int v[10];
int a[515][515],v2[11],v3[11];
int main(){
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
int n,i,j,st,dr,mij,ok,ok2,p1,p2,nr,h,s=0;
scanf("%d",&n);
for(i=1;i<=9;i++)
scanf("%d",&v[i]);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&a[i][j]);
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
for(h=1;h<=9;h++){
for(i=1;i<=n-2;i++){
for(j=1;j<=n-2;j++){
if(a[i][j]==v[h]){
for(int g=1;g<=9;g++){
for(int f=1;f<=9;f++){
if(g!=f&&g!=h&&f!=h){
st=j+1;
dr=n-1;
ok=0;
while(st<=dr&&ok!=1){
mij=(st+dr)/2;
nr=a[i][mij]-a[i][j];
if(nr==v[g]){
ok=1;
p1=mij;
}
else if(nr<v[g])
st=mij+1;
else
dr=mij-1;
}
st=i+1;
dr=n-1;
ok2=0;
while(st<=dr&&ok2!=1){
mij=(st+dr)/2;
nr=a[mij][j]-a[i][j];
if(nr==v[f]){
ok2=1;
p2=mij;
}
else if(nr<v[f])
st=mij+1;
else
dr=mij-1;
}
if(ok==1&&ok2==1){
v2[1]=a[i][n]-a[i][p1];
v2[2]=a[n][j]-a[p2][j];
v2[3]=a[p2][p1]-a[p2][j]-a[i][p1]+a[i][j];
v2[4]=a[p2][n]-a[p2][p1]-a[i][n]+a[i][p1];
v2[5]=a[n][p1]-a[n][j]-a[p2][p1]+a[p2][j];
v2[6]=a[n][n]-a[p2][n]-a[n][p1]+a[p2][p1];
v2[7]=v[h];
v2[8]=v[f];
v2[9]=v[g];
for(int w=1;w<=9;w++)
v3[w]=v[w];
sort(v2+1,v2+10);
sort(v3+1,v3+10);
int okk=0;
for(int w=1;w<=9;w++)
if(v2[w]!=v3[w])
okk=1;
if(okk==0&&s!=1){
printf("%d %d %d %d\n",i,p2,j,p1);
s=1;
}
}
}
}
}
}
}
}
}
return 0;
}