Cod sursa(job #2536112)
Utilizator | Data | 1 februarie 2020 15:18:24 | |
---|---|---|---|
Problema | Zone | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 3.74 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("zone.in");
ofstream out("zone.out");
int v[10],sum[257][257],va[6],vb[6];
bool ver[10];
int main() {
int n,x,i,r,pas,j,k;
in>>n;
for(i=1; i<=9; i++)
in>>v[i];
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) {
in>>x;
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
}
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
///for(k=1; k<=9; k++)
///ver[k]=0;
for(k=1; k<=9; k++)
if(sum[i][j]==v[k])
break;
if(k!=10) {
ver[k]=1; /// 1
for(k=1; k<=9; k++)
if(!ver[k]) {
r=j;
pas=1<<8;
while(pas) {
if(r+pas<=n&&sum[i][r+pas]-sum[i][j]<=v[k])
r+=pas;
pas/=2;
}
if(sum[i][r]-sum[i][j]==v[k]) {
int k1=k;
ver[k]=1;/// 2
for(k=1; k<=9; k++)
if(!ver[k]&&sum[i][n]-sum[i][r]==v[k])
break;
if(k!=10) {
ver[k]=1;/// 3
int k2=k;
for(k=1; k<=9; k++)
if(!ver[k]) {
int r1=i;
pas=1<<8;
while(pas) {
if(r1+pas<=n&&sum[r1+pas][j]-sum[i][j]<=v[k])
r1+=pas;
pas/=2;
}
if(sum[r1][j]-sum[i][j]==v[k]) {
ver[k]=1; /// 4
int cnt=0,k3=k;
for(k=1; k<=9; k++)
if(!ver[k])
va[++cnt]=v[k];
sort(va+1,va+cnt+1);
ver[k3]=0;
vb[1]=sum[n][j]-sum[r1][j]; /// 7
vb[2]=sum[r1][r]-sum[r1][j]-sum[i][r]+sum[i][j]; ///5
vb[3]=sum[r1][n]-sum[r1][r]-sum[i][n]+sum[i][r]; ///6
vb[4]=sum[n][r]-sum[r1][r]-sum[n][j]+sum[r1][j]; ///8
vb[5]=sum[n][n]-sum[n][r]-sum[r1][n]+sum[r1][r]; ///9
sort(vb+1,vb+7);
int s,t;
for(s=1,t=1; s<=6; s++)
if(va[s]==vb[t])
t++;
if(t==6) {
out<<i<<" "<<r1<<" "<<j<<" "<<r;
return 0;
}
}
}
ver[k2]=0;
}
ver[k1]=0;
}
}
}
}
}
return 0;
}