Cod sursa(job #2358589)
Utilizator | Data | 28 februarie 2019 10:32:40 | |
---|---|---|---|
Problema | Zone | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 4.87 kb |
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
long long a[515][515];int ok, s1, s2, s3, s4;
int n, m, i, j, l1, c1, l2, c2;long long sum5, sum6, sum7, sum8, sum9;
long long v[10];bool viz[10];
int valid (long long sum5,long long sum6,long long sum7,long long sum8,long long sum9)
{
for (int s5=1;s5<=9;s5++) {
if (viz[s5]==0 && sum5==v[s5]) {
viz[s5]=1;
for (int s6=1;s6<=9;s6++) {
if (viz[s6]==0 && sum6==v[s6]) {
viz[s6]=1;
for (int s7=1;s7<=9;s7++) {
if (viz[s7]==0 && sum7==v[s7]) {
viz[s7]=1;
for (int s8=1;s8<=9;s8++) {
if (viz[s8]==0 && sum8==v[s8]) {
viz[s8]=1;
for (int s9=1;s9<=9;s9++) {
if (viz[s9]==0 && sum9==v[s9])
return 1;
}
}
}
}
}
}
}
}
}
return 0;
}
int lcautbin(int st, int dr, int s2)
{
while (st<=dr) {
int mid=(st+dr)/2;
if (a[mid][c1]-a[l1][c1]==s2)
return mid;
if (a[mid][c1]-a[l1][c1]<s2)
st=mid+1;
else
dr=mid-1;
}
return 0;
}
int cautbin(int st, int dr, int l1, int s1)
{
int c=st;
while (st<=dr) {
int mid = (st+dr)/2;
if (a[l1][mid]-a[0][mid]-a[l1][c-1]+a[0][c-1]==s1)
return mid;
if (a[l1][mid]-a[0][mid]-a[l1][c-1]+a[0][c-1]<s1)
st=mid+1;
else
dr=mid-1;
}
return 0;
}
int main () {
ifstream fin ("zone.in");
ofstream fout ("zone.out");
fin>>n;
for (i=1;i<=9;i++) {
fin>>v[i];
}
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++)
fin>>a[i][j];
}
sort(v+1, v+9+1);
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
for (l1=1;l1<=n-2;l1++) {
memset (viz, 0, sizeof(viz));
for (s1=1;s1<=9;s1++) {
if (viz[s1]==0) {
c1=cautbin(1, n-2, l1, v[s1]);
if (c1!=0) {
viz[s1]=1;
for (s2=1;s2<=9;s2++) {
if (viz[s2]==0) {
c2=cautbin (c1+1, n-1, l1, v[s2]);
if (c2!=0) {
viz[s2]=1;
for (s3=1;s3<=9;s3++) {
if (viz[s3]==0) {
if (a[l1][n]-a[0][n]-a[l1][c2]+a[0][c2]==v[s3]){
viz[s3]=1;
ok=0;
for (s4=1;s4<=9;s4++) {
if (viz[s4]==0) {
l2=lcautbin(l1+1, n-1, v[s4]);
if (l2!=0) {
viz[s4]=1;
sum5=a[l2][c2]-a[l1][c2]-a[l2][c1]+a[l1][c1];
sum6=a[l2][n]-a[l1][n]-a[l2][c2]+a[l1][c2];
sum7=a[n][c1]-a[l2][c1]-a[n][0]+a[l2][0];
sum8=a[n][c2]-a[l2][c2]-a[n][c1]+a[l2][c1];
sum9=a[n][n]-a[l2][n]-a[n][c2]+a[l2][c2];
if (valid(sum5, sum6, sum7, sum8, sum9)) {
fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
return 0;
}
else
viz[s4]=0;
}
}
}
} else
viz[s3]=0;
}
}
}else
viz[s2]=0;
}
}
}else
viz[s1]=0;
}
}
}
return 0;
}